AtCoder Grand Contest 019

Submission #3058568

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;

const int N=10005,P=998244353,G=3;
int n,e,m,f[N],rf[N];
char a[N],b[N];

int pw(int a,int x)
{
	int ans=1;
	for(;x;x>>=1,a=1ll*a*a%P)
		if(x&1)ans=1ll*ans*a%P;
	return ans;
}

void dft(int *a,int n,int inv)
{
	for(int i=0,j=0;i<n;i++)
	{
		if(i>j)swap(a[i],a[j]);
		for(int k=n>>1;(j^=k)<k;k>>=1);
	}
	for(int i=2;i<=n;i<<=1)
	{
		int m=i>>1,wn=pw(G,P-1+inv*(P-1)/i);
		for(int *p=a;p<a+n;p+=i)
			for(int j=0,w=1;j<m;j++,w=1ll*w*wn%P)
			{
				int t=1ll*w*p[m+j]%P;
				p[m+j]=(p[j]-t)%P;
				p[j]=(p[j]+t)%P;
			}
	}
	if(inv==-1)
		for(int i=0,t=pw(n,P-2);i<n;i++)a[i]=1ll*a[i]*t%P;
}

typedef vector<int> poly;
poly operator*(const poly&a,const poly&b)
{
	poly c;
	static int ta[N<<2],tb[N<<2];
	copy(a.begin(),a.end(),ta);
	copy(b.begin(),b.end(),tb);
	int l=1;
	for(;l<=m<<1;l<<=1);
	dft(ta,l,1),dft(tb,l,1);
	for(int i=0;i<l;i++)ta[i]=1ll*ta[i]*tb[i]%P;
	dft(ta,l,-1);
	for(int i=0;i<=m;i++)c.push_back(ta[i]);
	for(int i=0;i<l;i++)ta[i]=tb[i]=0;
	return c;
}
poly power(poly a,int n)
{
	poly ans={1};
	for(;n;n>>=1,a=a*a)
		if(n&1)ans=ans*a;
	return ans;
}

int main()
{
	scanf("%s%s",a+1,b+1);
	n=strlen(a+1);
	for(int i=1;i<=n;i++)
	{
		e+=a[i]=='1'&&b[i]=='0';
		m+=a[i]=='1'&&b[i]=='1';
	}
	for(int i=f[0]=1;i<=n;i++)f[i]=1ll*f[i-1]*i%P;
	rf[n]=pw(f[n],P-2);
	for(int i=n;i;i--)rf[i-1]=1ll*rf[i]*i%P;
	poly a;
	for(int i=0;i<=m;i++)
		a.push_back(rf[i+1]);
	a=power(a,e);
	int ans=0;
	for(int i=0;i<=m;i++)ans=(ans+a[i])%P;
	ans=1ll*ans*f[e]%P*f[m]%P*f[e+m]%P;
	printf("%d\n",(ans+P)%P);
	return 0;
}

Submission

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

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:64:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s%s",a+1,b+1);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt,sample_04.txt
Partial 0 / 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 0 / 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 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 256 KB
subtask_1_03.txt AC 1 ms 256 KB
subtask_1_04.txt AC 1 ms 256 KB
subtask_1_05.txt AC 1 ms 256 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 1 ms 256 KB
subtask_1_08.txt AC 1 ms 256 KB
subtask_1_09.txt AC 1 ms 256 KB
subtask_1_10.txt AC 1 ms 256 KB
subtask_1_11.txt AC 1 ms 256 KB
subtask_1_12.txt AC 1 ms 256 KB
subtask_1_13.txt AC 1 ms 256 KB
subtask_1_14.txt WA
subtask_1_15.txt AC 1 ms 256 KB
subtask_1_16.txt AC 2 ms 256 KB
subtask_1_17.txt AC 2 ms 256 KB
subtask_1_18.txt AC 2 ms 256 KB
subtask_1_19.txt AC 2 ms 256 KB
subtask_1_20.txt AC 2 ms 256 KB
subtask_1_21.txt AC 2 ms 256 KB
subtask_1_22.txt AC 2 ms 256 KB
subtask_1_23.txt AC 2 ms 256 KB
subtask_1_24.txt AC 1 ms 256 KB
subtask_1_25.txt AC 1 ms 256 KB
subtask_1_26.txt AC 1 ms 256 KB
subtask_1_27.txt AC 2 ms 256 KB
subtask_1_28.txt AC 2 ms 256 KB
subtask_1_29.txt AC 2 ms 256 KB
subtask_1_30.txt AC 3 ms 256 KB
subtask_1_31.txt AC 2 ms 256 KB
subtask_1_32.txt AC 3 ms 256 KB
subtask_1_33.txt AC 1 ms 256 KB
subtask_1_34.txt AC 1 ms 256 KB
subtask_1_35.txt AC 2 ms 256 KB
subtask_1_36.txt AC 2 ms 256 KB
subtask_1_37.txt AC 3 ms 256 KB
subtask_1_38.txt AC 3 ms 256 KB
subtask_1_39.txt AC 2 ms 256 KB
subtask_1_40.txt AC 2 ms 256 KB
subtask_1_41.txt AC 2 ms 256 KB
subtask_1_42.txt AC 2 ms 256 KB
subtask_2_01.txt AC 1 ms 384 KB
subtask_2_02.txt AC 1 ms 384 KB
subtask_2_03.txt AC 4 ms 384 KB
subtask_2_04.txt AC 19 ms 512 KB
subtask_2_05.txt AC 24 ms 512 KB
subtask_2_06.txt WA
subtask_2_07.txt AC 13 ms 896 KB
subtask_2_08.txt AC 18 ms 896 KB
subtask_2_09.txt AC 50 ms 896 KB
subtask_2_10.txt AC 39 ms 640 KB
subtask_2_11.txt AC 47 ms 640 KB
subtask_2_12.txt AC 42 ms 640 KB
subtask_2_13.txt AC 44 ms 640 KB
subtask_2_14.txt AC 52 ms 640 KB
subtask_2_15.txt AC 47 ms 640 KB
subtask_2_16.txt AC 21 ms 512 KB
subtask_2_17.txt AC 26 ms 512 KB
subtask_2_18.txt AC 21 ms 512 KB
subtask_2_19.txt AC 1 ms 384 KB
subtask_2_20.txt AC 1 ms 384 KB
subtask_2_21.txt AC 1 ms 384 KB
subtask_2_22.txt AC 94 ms 896 KB
subtask_2_23.txt AC 99 ms 896 KB
subtask_2_24.txt AC 61 ms 896 KB
subtask_2_25.txt AC 67 ms 896 KB
subtask_2_26.txt AC 105 ms 896 KB
subtask_2_27.txt AC 99 ms 896 KB
subtask_2_28.txt AC 2 ms 384 KB
subtask_2_29.txt AC 2 ms 384 KB
subtask_2_30.txt AC 12 ms 384 KB
subtask_2_31.txt AC 23 ms 512 KB
subtask_2_32.txt AC 21 ms 512 KB
subtask_2_33.txt AC 44 ms 640 KB
subtask_2_34.txt AC 49 ms 640 KB
subtask_2_35.txt AC 40 ms 640 KB
subtask_2_36.txt AC 37 ms 640 KB
subtask_2_37.txt AC 78 ms 768 KB
subtask_2_38.txt AC 89 ms 896 KB