Submission #3058568


Source Code Expand

Copy
#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 Info

Submission Time
Task E - Shuffle and Swap
User luogu_bot2
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1559 Byte
Status
Exec Time 105 ms
Memory 896 KB

Compile Error

./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);
                       ^

Judge Result

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