Submission #5917285
Source Code Expand
#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 Info
Submission Time |
|
Task |
E - Shuffle and Swap |
User |
zhouzhendong |
Language |
C++14 (GCC 5.4.1) |
Score |
1700 |
Code Size |
4121 Byte |
Status |
AC |
Exec Time |
186 ms |
Memory |
2868 KB |
Judge Result
Set Name |
Sample |
Partial |
All |
Score / Max Score |
0 / 0 |
1200 / 1200 |
500 / 500 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
Partial |
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 |
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 |
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 |