Submission #1543579
Source Code Expand
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #include <functional> #include <map> #include <set> #include <cassert> #define SIZE 100005 #define FOR(i,n) for(int i = 0; i < (n); i++) #define sz(c) ((int)(c).size()) #define ten(x) ((int)1e##x) #define MOD 998244353 using namespace std; typedef long long int ll; typedef pair <int,int> P; template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; } template<class T> T mod_inv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; } ll mod_pow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; } template<int mod, int primitive_root> class NTT { public: int get_mod() const { return mod; } void _ntt(vector<ll>& a, int sign) { const int n = sz(a); assert((n ^ (n&-n)) == 0); //n = 2^k const int g = 3; //g is primitive root of mod int h = (int)mod_pow(g, (mod - 1) / n, mod); // h^n = 1 if (sign == -1) h = (int)mod_inv(h, mod); //h = h^-1 % mod //bit reverse int i = 0; for (int j = 1; j < n - 1; ++j) { for (int k = n >> 1; k >(i ^= k); k >>= 1); if (j < i) swap(a[i], a[j]); } for (int m = 1; m < n; m *= 2) { const int m2 = 2 * m; const ll base = mod_pow(h, n / m2, mod); ll w = 1; FOR(x, m) { for (int s = x; s < n; s += m2) { ll u = a[s]; ll d = a[s + m] * w % mod; a[s] = u + d; if (a[s] >= mod) a[s] -= mod; a[s + m] = u - d; if (a[s + m] < 0) a[s + m] += mod; } w = w * base % mod; } } for (auto& x : a) if (x < 0) x += mod; } void ntt(vector<ll>& input) { _ntt(input, 1); } void intt(vector<ll>& input) { _ntt(input, -1); const int n_inv = mod_inv(sz(input), mod); for (auto& x : input) x = x * n_inv % mod; } // 畳み込み演算を行う vector<ll> convolution(const vector<ll>& a, const vector<ll>& b){ int ntt_size = 1; while (ntt_size < sz(a) + sz(b)) ntt_size *= 2; vector<ll> _a = a, _b = b; _a.resize(ntt_size); _b.resize(ntt_size); ntt(_a); ntt(_b); FOR(i, ntt_size){ (_a[i] *= _b[i]) %= mod; } intt(_a); return _a; } }; NTT <MOD,3> run; ll inv[SIZE],fac[SIZE],finv[SIZE]; void make() { fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; for(int i=2;i<SIZE;i++) { inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD; fac[i]=fac[i-1]*(ll) i%MOD; finv[i]=finv[i-1]*inv[i]%MOD; } } ll C(int a,int b) { if(a<b) return 0; return fac[a]*(finv[b]*finv[a-b]%MOD)%MOD; } char A[SIZE],B[SIZE]; ll dp1[SIZE]; int a,b; void mpow(int t) { if(t==0) { for(int i=0;i<=a+b;i++) dp1[i]=0; dp1[0]=1; } else { mpow(t/2); vector <ll> A; for(int i=0;i<=a+b;i++) A.push_back(dp1[i]); vector <ll> B=run.convolution(A,A); for(int i=0;i<=a+b;i++) dp1[i]=B[i]; if(t%2==1) { vector <ll> C; for(int i=0;i<=a+b;i++) C.push_back(finv[i]); C[0]=0; for(int i=0;i<=a+b;i++) A[i]=dp1[i]; B=run.convolution(A,C); for(int i=0;i<=a+b;i++) dp1[i]=B[i]; } } } int main() { make(); scanf("%s",&A); scanf("%s",&B); int n=strlen(A); a=0,b=0; for(int i=0;i<n;i++) { if(A[i]=='1') { if(B[i]=='1') b++; else a++; } } //printf("* %d %d\n",a,b); mpow(a); ll ret=0; for(int i=a;i<=a+b;i++) { int zan=b-(i-a); ll way=C(b,zan); way=way*fac[zan]%MOD*fac[zan]%MOD; way=way*fac[i-a]%MOD*dp1[i]%MOD*fac[i]%MOD; way=way*C(i+zan,zan)%MOD; ret+=way; if(ret>=MOD) ret-=MOD; //printf("%d %lld\n",i,way); } printf("%lld\n",ret*fac[a]%MOD); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Shuffle and Swap |
User | yutaka1999 |
Language | C++14 (GCC 5.4.1) |
Score | 1700 |
Code Size | 3826 Byte |
Status | AC |
Exec Time | 208 ms |
Memory | 3916 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:142:15: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘char (*)[100005]’ [-Wformat=] scanf("%s",&A); ^ ./Main.cpp:143:15: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘char (*)[100005]’ [-Wformat=] scanf("%s",&B); ^ ./Main.cpp:142:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s",&A); ^ ./Main.cpp:143:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s",&B); ^
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 | 3 ms | 2560 KB |
sample_02.txt | AC | 3 ms | 2560 KB |
sample_03.txt | AC | 3 ms | 2560 KB |
sample_04.txt | AC | 3 ms | 2560 KB |
subtask_1_01.txt | AC | 3 ms | 2560 KB |
subtask_1_02.txt | AC | 3 ms | 2560 KB |
subtask_1_03.txt | AC | 3 ms | 2560 KB |
subtask_1_04.txt | AC | 3 ms | 2560 KB |
subtask_1_05.txt | AC | 3 ms | 2560 KB |
subtask_1_06.txt | AC | 3 ms | 2560 KB |
subtask_1_07.txt | AC | 3 ms | 2560 KB |
subtask_1_08.txt | AC | 3 ms | 2560 KB |
subtask_1_09.txt | AC | 3 ms | 2560 KB |
subtask_1_10.txt | AC | 3 ms | 2560 KB |
subtask_1_11.txt | AC | 3 ms | 2560 KB |
subtask_1_12.txt | AC | 4 ms | 2560 KB |
subtask_1_13.txt | AC | 4 ms | 2560 KB |
subtask_1_14.txt | AC | 3 ms | 2560 KB |
subtask_1_15.txt | AC | 3 ms | 2688 KB |
subtask_1_16.txt | AC | 4 ms | 2688 KB |
subtask_1_17.txt | AC | 5 ms | 2688 KB |
subtask_1_18.txt | AC | 5 ms | 2688 KB |
subtask_1_19.txt | AC | 5 ms | 2688 KB |
subtask_1_20.txt | AC | 5 ms | 2688 KB |
subtask_1_21.txt | AC | 5 ms | 2688 KB |
subtask_1_22.txt | AC | 6 ms | 2688 KB |
subtask_1_23.txt | AC | 6 ms | 2688 KB |
subtask_1_24.txt | AC | 4 ms | 2560 KB |
subtask_1_25.txt | AC | 4 ms | 2560 KB |
subtask_1_26.txt | AC | 5 ms | 2560 KB |
subtask_1_27.txt | AC | 6 ms | 2688 KB |
subtask_1_28.txt | AC | 5 ms | 2688 KB |
subtask_1_29.txt | AC | 5 ms | 2688 KB |
subtask_1_30.txt | AC | 6 ms | 2688 KB |
subtask_1_31.txt | AC | 5 ms | 2688 KB |
subtask_1_32.txt | AC | 6 ms | 2688 KB |
subtask_1_33.txt | AC | 6 ms | 2688 KB |
subtask_1_34.txt | AC | 6 ms | 2688 KB |
subtask_1_35.txt | AC | 6 ms | 2688 KB |
subtask_1_36.txt | AC | 6 ms | 2688 KB |
subtask_1_37.txt | AC | 6 ms | 2688 KB |
subtask_1_38.txt | AC | 6 ms | 2688 KB |
subtask_1_39.txt | AC | 6 ms | 2688 KB |
subtask_1_40.txt | AC | 6 ms | 2688 KB |
subtask_1_41.txt | AC | 6 ms | 2688 KB |
subtask_1_42.txt | AC | 6 ms | 2688 KB |
subtask_2_01.txt | AC | 3 ms | 2560 KB |
subtask_2_02.txt | AC | 3 ms | 2560 KB |
subtask_2_03.txt | AC | 9 ms | 2688 KB |
subtask_2_04.txt | AC | 76 ms | 3320 KB |
subtask_2_05.txt | AC | 97 ms | 3260 KB |
subtask_2_06.txt | AC | 4 ms | 2688 KB |
subtask_2_07.txt | AC | 19 ms | 3808 KB |
subtask_2_08.txt | AC | 30 ms | 3808 KB |
subtask_2_09.txt | AC | 97 ms | 3864 KB |
subtask_2_10.txt | AC | 162 ms | 3876 KB |
subtask_2_11.txt | AC | 196 ms | 3876 KB |
subtask_2_12.txt | AC | 174 ms | 3876 KB |
subtask_2_13.txt | AC | 88 ms | 3344 KB |
subtask_2_14.txt | AC | 103 ms | 3352 KB |
subtask_2_15.txt | AC | 93 ms | 3356 KB |
subtask_2_16.txt | AC | 87 ms | 3324 KB |
subtask_2_17.txt | AC | 108 ms | 3324 KB |
subtask_2_18.txt | AC | 87 ms | 3324 KB |
subtask_2_19.txt | AC | 95 ms | 3288 KB |
subtask_2_20.txt | AC | 100 ms | 3288 KB |
subtask_2_21.txt | AC | 91 ms | 3288 KB |
subtask_2_22.txt | AC | 187 ms | 3916 KB |
subtask_2_23.txt | AC | 197 ms | 3916 KB |
subtask_2_24.txt | AC | 119 ms | 3816 KB |
subtask_2_25.txt | AC | 130 ms | 3868 KB |
subtask_2_26.txt | AC | 208 ms | 3912 KB |
subtask_2_27.txt | AC | 198 ms | 3904 KB |
subtask_2_28.txt | AC | 105 ms | 3344 KB |
subtask_2_29.txt | AC | 86 ms | 3288 KB |
subtask_2_30.txt | AC | 101 ms | 3304 KB |
subtask_2_31.txt | AC | 93 ms | 3324 KB |
subtask_2_32.txt | AC | 87 ms | 3324 KB |
subtask_2_33.txt | AC | 87 ms | 3324 KB |
subtask_2_34.txt | AC | 98 ms | 3344 KB |
subtask_2_35.txt | AC | 164 ms | 3908 KB |
subtask_2_36.txt | AC | 152 ms | 3908 KB |
subtask_2_37.txt | AC | 153 ms | 3876 KB |
subtask_2_38.txt | AC | 175 ms | 3908 KB |