AtCoder Grand Contest 019

Submission #5917285

Source codeソースコード

#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"---------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
						For(_x,L,R)cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef vector <int> vi;
LL read(){
	LL x=0,f=0;
	char ch=getchar();
	while (!isdigit(ch))
		f|=ch=='-',ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int N=1<<16,mod=998244353;
int Pow(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(LL)x*x%mod)
		if (y&1)
			ans=(LL)ans*x%mod;
	return ans;
}
void Add(int &x,int y){
	if ((x+=y)>=mod)
		x-=mod;
}
void Del(int &x,int y){
	if ((x-=y)<0)
		x+=mod;
}
int Add(int x){
	return x>=mod?x-mod:x;
}
int Del(int x){
	return x<0?x+mod:x;
}
int n,m,c,d;
void IN(){
	static char s[N];
	static int a[N],b[N];
	cin>>s+1;
	n=strlen(s+1);
	For(i,1,n)
		a[i]=s[i]-'0';
	cin>>s+1;
	For(i,1,n)
		b[i]=s[i]-'0';
	For(i,1,n)
		if (a[i]&&!b[i])
			c++;
		else if (a[i]&&b[i])
			d++;
}
namespace fft{
	int w[N],R[N];
	void init(int n){
		int d=0;
		while ((1<<d)<n)
			d++;
		w[0]=1,w[1]=Pow(3,(mod-1)>>d);
		For(i,2,n-1)
			w[i]=(LL)w[i-1]*w[1]%mod;
		For(i,0,n-1)
			R[i]=(R[i>>1]>>1)|((i&1)<<(d-1));
	}
	void FFT(int *a,int n,int flag){
		For(i,0,n-1)
			if (i<R[i])
				swap(a[i],a[R[i]]);
		for (int t=n>>1,d=1;d<n;d<<=1,t>>=1)
			for (int i=0;i<n;i+=d<<1)
				for (int j=0;j<d;j++){
					int tmp=(LL)w[t*j]*a[i+j+d]%mod;
					a[i+j+d]=Del(a[i+j]-tmp);
					Add(a[i+j],tmp);
				}
		if (flag<0){
			reverse(a+1,a+n);
			int inv=Pow(n,mod-2);
			For(i,0,n-1)
				a[i]=(LL)a[i]*inv%mod;
		}
	}
}
using fft::FFT;
int Fac[N],Inv[N],Iv[N];
void prework(){
	int n=N-1;
	for (int i=Fac[0]=1;i<=n;i++)
		Fac[i]=(LL)Fac[i-1]*i%mod;
	Inv[n]=Pow(Fac[n],mod-2);
	Fod(i,n,1)
		Inv[i-1]=(LL)Inv[i]*i%mod;
	For(i,1,n)
		Iv[i]=(LL)Inv[i]*Fac[i-1]%mod;
}
vi Fix(vi a,int n){
	a.resize(n,0);
	return a;
}
vi operator + (vi a,vi b){
	int n=max(a.size(),b.size());
	a=Fix(a,n),b=Fix(b,n);
	For(i,0,n-1)
		Add(a[i],b[i]);
	return a;
}
vi operator - (vi a,vi b){
	int n=max(a.size(),b.size());
	a=Fix(a,n),b=Fix(b,n);
	For(i,0,n-1)
		Del(a[i],b[i]);
	return a;
}
vi operator * (vi a,vi b){
	int n=1,m=a.size()+b.size()-1;
	while (n<a.size()+b.size())
		n<<=1;
	a=Fix(a,n),b=Fix(b,n);
	fft::init(n),FFT(&a[0],n,1),FFT(&b[0],n,1);
	For(i,0,n-1)
		a[i]=(LL)a[i]*b[i]%mod;
	FFT(&a[0],n,-1);
	return Fix(a,m);
}
vi Der(vi a){
	int n=(int)a.size()-1;
	For(i,0,n-1)
		a[i]=(LL)a[i+1]*(i+1)%mod;
	return Fix(a,n);
}
vi Int(vi a){
	int n=(int)a.size();
	a.pb(0);
	Fod(i,n,1)
		a[i]=(LL)a[i-1]*Iv[i]%mod;
	a[0]=0;
	return a;
}
vi inv(vi a){
	int n=a.size();
	if (n==1)
		return (vi){Pow(a[0],mod-2)};
	vi b=inv(Fix(a,(n+1)>>1));
	return Fix(b+b-a*b*b,n);
}
vi Ln(vi a){
	int n=a.size();
	return Int(Fix(Der(a)*inv(a),n-1));
}
vi Exp(vi a){
	int n=a.size();
	if (n==1)
		return (vi){1};
	vi b=Fix(Exp(Fix(a,(n+1)>>1)),n);
	return Fix(b*((vi){1}-Ln(b)+a),n);
}
vi Pow(vi a,int b){
	int n=a.size();
	a=Ln(a);
	For(i,0,n-1)
		a[i]=(LL)a[i]*b%mod;
	return Exp(a);
}
void Test(){
	int n=read();
	vi a(n);
	For(i,0,n-1)
		a[i]=read();
	vi b=a*a;
	outarr(b,0,b.size()-1);
	b=Der(a);
	outarr(b,0,b.size()-1);
	b=Int(a);
	outarr(b,0,b.size()-1);
	b=inv(a);
	outarr(b,0,b.size()-1);
	b=Ln(a);
	outarr(b,0,b.size()-1);
	b=Exp(a);
	outarr(b,0,b.size()-1);
}
int main(){
	prework();
//	Test();
	IN();
	n=d+1;
	vi tmp(n);
	vi x(n);
	For(i,1,n-1)
		x[i]=Iv[i];
	vi a=Exp(Fix(x,n));
	vi e=Exp(Fix((vi){0,1},n+1))-(vi){1};
	For(i,0,n-1)
		e[i]=e[i+1];
	e=Fix(e,n);
	vi b=Pow(e,c);
	a=Fix(a*b,n);
	int ans=(LL)a[d]*Fac[c]%mod*Fac[d]%mod*Fac[c+d]%mod;
	cout<<ans<<endl;
	return 0;
}

Submission

Task問題 E - Shuffle and Swap
User nameユーザ名 zhouzhendong
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1700
Source lengthソースコード長 4121 Byte
File nameファイル名
Exec time実行時間 186 ms
Memory usageメモリ使用量 2868 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt,sample_04.txt
Partial 1200 / 1200 sample_01.txt,sample_02.txt,sample_03.txt,sample_04.txt,subtask_1_01.txt,subtask_1_02.txt,subtask_1_03.txt,subtask_1_04.txt,subtask_1_05.txt,subtask_1_06.txt,subtask_1_07.txt,subtask_1_08.txt,subtask_1_09.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_12.txt,subtask_1_13.txt,subtask_1_14.txt,subtask_1_15.txt,subtask_1_16.txt,subtask_1_17.txt,subtask_1_18.txt,subtask_1_19.txt,subtask_1_20.txt,subtask_1_21.txt,subtask_1_22.txt,subtask_1_23.txt,subtask_1_24.txt,subtask_1_25.txt,subtask_1_26.txt,subtask_1_27.txt,subtask_1_28.txt,subtask_1_29.txt,subtask_1_30.txt,subtask_1_31.txt,subtask_1_32.txt,subtask_1_33.txt,subtask_1_34.txt,subtask_1_35.txt,subtask_1_36.txt,subtask_1_37.txt,subtask_1_38.txt,subtask_1_39.txt,subtask_1_40.txt,subtask_1_41.txt,subtask_1_42.txt
All 500 / 500 sample_01.txt,sample_02.txt,sample_03.txt,sample_04.txt,sample_01.txt,sample_02.txt,sample_03.txt,sample_04.txt,subtask_1_01.txt,subtask_1_02.txt,subtask_1_03.txt,subtask_1_04.txt,subtask_1_05.txt,subtask_1_06.txt,subtask_1_07.txt,subtask_1_08.txt,subtask_1_09.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_12.txt,subtask_1_13.txt,subtask_1_14.txt,subtask_1_15.txt,subtask_1_16.txt,subtask_1_17.txt,subtask_1_18.txt,subtask_1_19.txt,subtask_1_20.txt,subtask_1_21.txt,subtask_1_22.txt,subtask_1_23.txt,subtask_1_24.txt,subtask_1_25.txt,subtask_1_26.txt,subtask_1_27.txt,subtask_1_28.txt,subtask_1_29.txt,subtask_1_30.txt,subtask_1_31.txt,subtask_1_32.txt,subtask_1_33.txt,subtask_1_34.txt,subtask_1_35.txt,subtask_1_36.txt,subtask_1_37.txt,subtask_1_38.txt,subtask_1_39.txt,subtask_1_40.txt,subtask_1_41.txt,subtask_1_42.txt,subtask_2_01.txt,subtask_2_02.txt,subtask_2_03.txt,subtask_2_04.txt,subtask_2_05.txt,subtask_2_06.txt,subtask_2_07.txt,subtask_2_08.txt,subtask_2_09.txt,subtask_2_10.txt,subtask_2_11.txt,subtask_2_12.txt,subtask_2_13.txt,subtask_2_14.txt,subtask_2_15.txt,subtask_2_16.txt,subtask_2_17.txt,subtask_2_18.txt,subtask_2_19.txt,subtask_2_20.txt,subtask_2_21.txt,subtask_2_22.txt,subtask_2_23.txt,subtask_2_24.txt,subtask_2_25.txt,subtask_2_26.txt,subtask_2_27.txt,subtask_2_28.txt,subtask_2_29.txt,subtask_2_30.txt,subtask_2_31.txt,subtask_2_32.txt,subtask_2_33.txt,subtask_2_34.txt,subtask_2_35.txt,subtask_2_36.txt,subtask_2_37.txt,subtask_2_38.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 8 ms 1660 KB
sample_02.txt AC 2 ms 1024 KB
sample_03.txt AC 2 ms 1024 KB
sample_04.txt AC 2 ms 1024 KB
subtask_1_01.txt AC 2 ms 1024 KB
subtask_1_02.txt AC 2 ms 1024 KB
subtask_1_03.txt AC 2 ms 1024 KB
subtask_1_04.txt AC 2 ms 1024 KB
subtask_1_05.txt AC 2 ms 1024 KB
subtask_1_06.txt AC 2 ms 1024 KB
subtask_1_07.txt AC 2 ms 1024 KB
subtask_1_08.txt AC 2 ms 1024 KB
subtask_1_09.txt AC 2 ms 1024 KB
subtask_1_10.txt AC 2 ms 1024 KB
subtask_1_11.txt AC 2 ms 1024 KB
subtask_1_12.txt AC 3 ms 1024 KB
subtask_1_13.txt AC 3 ms 1024 KB
subtask_1_14.txt AC 6 ms 1152 KB
subtask_1_15.txt AC 7 ms 1152 KB
subtask_1_16.txt AC 7 ms 1152 KB
subtask_1_17.txt AC 7 ms 1152 KB
subtask_1_18.txt AC 7 ms 1152 KB
subtask_1_19.txt AC 6 ms 1024 KB
subtask_1_20.txt AC 7 ms 1152 KB
subtask_1_21.txt AC 6 ms 1024 KB
subtask_1_22.txt AC 5 ms 1024 KB
subtask_1_23.txt AC 4 ms 1024 KB
subtask_1_24.txt AC 2 ms 1024 KB
subtask_1_25.txt AC 2 ms 1024 KB
subtask_1_26.txt AC 2 ms 1024 KB
subtask_1_27.txt AC 5 ms 1024 KB
subtask_1_28.txt AC 5 ms 1024 KB
subtask_1_29.txt AC 5 ms 1024 KB
subtask_1_30.txt AC 6 ms 1024 KB
subtask_1_31.txt AC 6 ms 1152 KB
subtask_1_32.txt AC 6 ms 1024 KB
subtask_1_33.txt AC 2 ms 1024 KB
subtask_1_34.txt AC 3 ms 1024 KB
subtask_1_35.txt AC 5 ms 1024 KB
subtask_1_36.txt AC 5 ms 1024 KB
subtask_1_37.txt AC 6 ms 1024 KB
subtask_1_38.txt AC 6 ms 1024 KB
subtask_1_39.txt AC 3 ms 1024 KB
subtask_1_40.txt AC 4 ms 1024 KB
subtask_1_41.txt AC 4 ms 1024 KB
subtask_1_42.txt AC 4 ms 1024 KB
subtask_2_01.txt AC 3 ms 1152 KB
subtask_2_02.txt AC 3 ms 1152 KB
subtask_2_03.txt AC 11 ms 1280 KB
subtask_2_04.txt AC 50 ms 1600 KB
subtask_2_05.txt AC 49 ms 1596 KB
subtask_2_06.txt AC 155 ms 2868 KB
subtask_2_07.txt AC 183 ms 2856 KB
subtask_2_08.txt AC 186 ms 2860 KB
subtask_2_09.txt AC 185 ms 2780 KB
subtask_2_10.txt AC 104 ms 2160 KB
subtask_2_11.txt AC 104 ms 2148 KB
subtask_2_12.txt AC 104 ms 2144 KB
subtask_2_13.txt AC 86 ms 1960 KB
subtask_2_14.txt AC 87 ms 1936 KB
subtask_2_15.txt AC 86 ms 2004 KB
subtask_2_16.txt AC 49 ms 1588 KB
subtask_2_17.txt AC 49 ms 1604 KB
subtask_2_18.txt AC 49 ms 1620 KB
subtask_2_19.txt AC 3 ms 1152 KB
subtask_2_20.txt AC 3 ms 1152 KB
subtask_2_21.txt AC 3 ms 1152 KB
subtask_2_22.txt AC 184 ms 2836 KB
subtask_2_23.txt AC 184 ms 2792 KB
subtask_2_24.txt AC 184 ms 2840 KB
subtask_2_25.txt AC 184 ms 2836 KB
subtask_2_26.txt AC 184 ms 2720 KB
subtask_2_27.txt AC 183 ms 2704 KB
subtask_2_28.txt AC 3 ms 1152 KB
subtask_2_29.txt AC 5 ms 1152 KB
subtask_2_30.txt AC 21 ms 1280 KB
subtask_2_31.txt AC 49 ms 1692 KB
subtask_2_32.txt AC 60 ms 1808 KB
subtask_2_33.txt AC 84 ms 1892 KB
subtask_2_34.txt AC 84 ms 1896 KB
subtask_2_35.txt AC 104 ms 2268 KB
subtask_2_36.txt AC 128 ms 2352 KB
subtask_2_37.txt AC 182 ms 2652 KB
subtask_2_38.txt AC 182 ms 2764 KB