結果
問題 | No.1655 123 Swaps |
ユーザー | sigma425 |
提出日時 | 2021-08-21 01:14:37 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 238 ms / 2,000 ms |
コード長 | 9,026 bytes |
コンパイル時間 | 2,447 ms |
コンパイル使用メモリ | 212,868 KB |
実行使用メモリ | 31,020 KB |
最終ジャッジ日時 | 2024-10-14 09:58:38 |
合計ジャッジ時間 | 8,186 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 18 ms
14,976 KB |
testcase_01 | AC | 18 ms
14,900 KB |
testcase_02 | AC | 18 ms
14,948 KB |
testcase_03 | AC | 20 ms
14,976 KB |
testcase_04 | AC | 20 ms
14,796 KB |
testcase_05 | AC | 18 ms
14,920 KB |
testcase_06 | AC | 20 ms
14,928 KB |
testcase_07 | AC | 19 ms
14,848 KB |
testcase_08 | AC | 19 ms
14,976 KB |
testcase_09 | AC | 19 ms
14,976 KB |
testcase_10 | AC | 19 ms
14,952 KB |
testcase_11 | AC | 19 ms
14,908 KB |
testcase_12 | AC | 19 ms
14,904 KB |
testcase_13 | AC | 18 ms
14,916 KB |
testcase_14 | AC | 20 ms
14,912 KB |
testcase_15 | AC | 234 ms
30,872 KB |
testcase_16 | AC | 233 ms
30,744 KB |
testcase_17 | AC | 232 ms
30,840 KB |
testcase_18 | AC | 238 ms
30,944 KB |
testcase_19 | AC | 236 ms
30,892 KB |
testcase_20 | AC | 232 ms
31,020 KB |
testcase_21 | AC | 233 ms
30,768 KB |
testcase_22 | AC | 229 ms
30,788 KB |
testcase_23 | AC | 235 ms
30,920 KB |
testcase_24 | AC | 238 ms
30,944 KB |
testcase_25 | AC | 234 ms
30,792 KB |
testcase_26 | AC | 147 ms
23,780 KB |
testcase_27 | AC | 136 ms
23,700 KB |
testcase_28 | AC | 135 ms
23,820 KB |
testcase_29 | AC | 146 ms
23,596 KB |
testcase_30 | AC | 145 ms
23,732 KB |
testcase_31 | AC | 136 ms
23,744 KB |
testcase_32 | AC | 18 ms
14,912 KB |
testcase_33 | AC | 19 ms
14,976 KB |
testcase_34 | AC | 19 ms
14,936 KB |
testcase_35 | AC | 73 ms
19,376 KB |
testcase_36 | AC | 79 ms
19,372 KB |
testcase_37 | AC | 81 ms
19,380 KB |
testcase_38 | AC | 132 ms
23,872 KB |
testcase_39 | AC | 141 ms
23,728 KB |
testcase_40 | AC | 144 ms
23,804 KB |
testcase_41 | AC | 19 ms
14,960 KB |
testcase_42 | AC | 18 ms
14,848 KB |
testcase_43 | AC | 19 ms
14,976 KB |
testcase_44 | AC | 19 ms
14,976 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using uint = unsigned int; using ull = unsigned long long; #define rep(i,n) for(int i=0;i<int(n);i++) #define rep1(i,n) for(int i=1;i<=int(n);i++) #define per(i,n) for(int i=int(n)-1;i>=0;i--) #define per1(i,n) for(int i=int(n);i>0;i--) #define all(c) c.begin(),c.end() #define si(x) int(x.size()) #define pb emplace_back #define fs first #define sc second template<class T> using V = vector<T>; template<class T> using VV = vector<vector<T>>; template<class T,class U> void chmax(T& x, U y){if(x<y) x=y;} template<class T,class U> void chmin(T& x, U y){if(y<x) x=y;} template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());} template<class T> int lwb(const V<T>& v, const T& a){return lower_bound(all(v),a) - v.begin();} template<class T> V<T> Vec(size_t a) { return V<T>(a); } template<class T, class... Ts> auto Vec(size_t a, Ts... ts) { return V<decltype(Vec<T>(ts...))>(a, Vec<T>(ts...)); } template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){ return o<<"("<<p.fs<<","<<p.sc<<")"; } template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){ o<<"{"; for(const T& v:vc) o<<v<<","; o<<"}"; return o; } constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); } #ifdef LOCAL #define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl void dmpr(ostream& os){os<<endl;} template<class T,class... Args> void dmpr(ostream&os,const T&t,const Args&... args){ os<<t<<" ~ "; dmpr(os,args...); } #define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__) #define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {"; \ for(auto v: x) cerr << v << ","; cerr << "}" << endl; #else #define show(x) void(0) #define dump(x) void(0) #define shows(...) void(0) #endif template<unsigned int mod_> struct ModInt{ using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr static uint mod = mod_; uint v; ModInt():v(0){} ModInt(ll _v):v(normS(_v%mod+mod)){} explicit operator bool() const {return v!=0;} static uint normS(const uint &x){return (x<mod)?x:x-mod;} // [0 , 2*mod-1] -> [0 , mod-1] static ModInt make(const uint &x){ModInt m; m.v=x; return m;} ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));} ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));} ModInt operator-() const { return make(normS(mod-v)); } ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);} ModInt operator/(const ModInt& b) const { return *this*b.inv();} ModInt& operator+=(const ModInt& b){ return *this=*this+b;} ModInt& operator-=(const ModInt& b){ return *this=*this-b;} ModInt& operator*=(const ModInt& b){ return *this=*this*b;} ModInt& operator/=(const ModInt& b){ return *this=*this/b;} ModInt& operator++(int){ return *this=*this+1;} ModInt& operator--(int){ return *this=*this-1;} ModInt pow(ll p) const { if(p<0) return inv().pow(-p); ModInt a = 1; ModInt x = *this; while(p){ if(p&1) a *= x; x *= x; p >>= 1; } return a; } ModInt inv() const { // should be prime return pow(mod-2); } // ll extgcd(ll a,ll b,ll &x,ll &y) const{ // ll p[]={a,1,0},q[]={b,0,1}; // while(*q){ // ll t=*p/ *q; // rep(i,3) swap(p[i]-=t*q[i],q[i]); // } // if(p[0]<0) rep(i,3) p[i]=-p[i]; // x=p[1],y=p[2]; // return p[0]; // } // ModInt inv() const { // ll x,y; // extgcd(v,mod,x,y); // return make(normS(x+mod)); // } bool operator==(const ModInt& b) const { return v==b.v;} bool operator!=(const ModInt& b) const { return v!=b.v;} bool operator<(const ModInt& b) const { return v<b.v;} friend istream& operator>>(istream &o,ModInt& x){ ll tmp; o>>tmp; x=ModInt(tmp); return o; } friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;} }; using mint = ModInt<924844033>; V<mint> fact,ifact,invs; mint Choose(int a,int b){ if(b<0 || a<b) return 0; return fact[a] * ifact[b] * ifact[a-b]; } void InitFact(int N){ //[0,N] N++; fact.resize(N); ifact.resize(N); invs.resize(N); fact[0] = 1; rep1(i,N-1) fact[i] = fact[i-1] * i; ifact[N-1] = fact[N-1].inv(); for(int i=N-2;i>=0;i--) ifact[i] = ifact[i+1] * (i+1); rep1(i,N-1) invs[i] = fact[i-1] * ifact[i]; } // inplace_fmt (without bit rearranging) // fft: // a[rev(i)] <- \sum_j \zeta^{ij} a[j] // invfft: // a[i] <- (1/n) \sum_j \zeta^{-ij} a[rev(j)] // These two are inversions. void fft(V<mint>& a){ static constexpr uint mod = mint::mod; static constexpr uint mod2 = mod + mod; static const int H = 21; // ord_2 (mod-1) static const mint root = 5; // primitive root of (Z/pZ)* static mint magic[H-1]; int n = si(a); assert(!(n & (n-1))); assert(n >= 1); assert(n <= 1<<H); // n should be power of 2 if(!magic[0]){ // precalc rep(i,H-1){ mint w = -root.pow(((mod-1)>>(i+2))*3); magic[i] = w; } } int m = n; if(m >>= 1){ rep(i,m){ uint v = a[i+m].v; // < M a[i+m].v = a[i].v + mod - v; // < 2M a[i].v += v; // < 2M } } if(m >>= 1){ mint p = 1; for(int h=0,s=0; s<n; s += m*2){ for(int i=s;i<s+m;i++){ uint v = (a[i+m] * p).v; // < M a[i+m].v = a[i].v + mod - v; // < 3M a[i].v += v; // < 3M } p *= magic[__builtin_ctz(++h)]; } } while(m){ if(m >>= 1){ mint p = 1; for(int h=0,s=0; s<n; s += m*2){ for(int i=s;i<s+m;i++){ uint v = (a[i+m] * p).v; // < M a[i+m].v = a[i].v + mod - v; // < 4M a[i].v += v; // < 4M } p *= magic[__builtin_ctz(++h)]; } } if(m >>= 1){ mint p = 1; for(int h=0,s=0; s<n; s += m*2){ for(int i=s;i<s+m;i++){ uint v = (a[i+m] * p).v; // < M a[i].v = (a[i].v >= mod2) ? a[i].v - mod2 : a[i].v; // < 2M a[i+m].v = a[i].v + mod - v; // < 3M a[i].v += v; // < 3M } p *= magic[__builtin_ctz(++h)]; } } } rep(i,n){ a[i].v = (a[i].v >= mod2) ? a[i].v - mod2 : a[i].v; // < 2M a[i].v = (a[i].v >= mod) ? a[i].v - mod : a[i].v; // < M } // finally < mod !! } void invfft(V<mint>& a){ static constexpr uint mod = mint::mod; static constexpr uint mod2 = mod + mod; static const int H = 21; // ord_2 (mod-1) static const mint root = 5; // primitive root of (Z/pZ)* static mint magic[H-1]; int n = si(a); assert(!(n & (n-1))); assert(n >= 1); assert(n <= 1<<H); // n should be power of 2 if(!magic[0]){ // precalc rep(i,H-1){ mint w = -root.pow(((mod-1)>>(i+2))*3); magic[i] = w.inv(); } } int m = 1; if(m < n>>1){ mint p = 1; for(int h=0,s=0; s<n; s += m*2){ for(int i=s;i<s+m;i++){ ull x = a[i].v + mod - a[i+m].v; // < 2M a[i].v += a[i+m].v; // < 2M a[i+m].v = (p.v * x) % mod; // < M } p *= magic[__builtin_ctz(++h)]; } m <<= 1; } for(;m < n>>1; m <<= 1){ mint p = 1; for(int h=0,s=0; s<n; s+= m*2){ for(int i=s;i<s+(m>>1);i++){ ull x = a[i].v + mod2 - a[i+m].v; // < 4M a[i].v += a[i+m].v; // < 4M a[i].v = (a[i].v >= mod2) ? a[i].v - mod2 : a[i].v; // < 2M a[i+m].v = (p.v * x) % mod; // < M } for(int i=s+(m>>1); i<s+m; i++){ ull x = a[i].v + mod - a[i+m].v; // < 2M a[i].v += a[i+m].v; // < 2M a[i+m].v = (p.v * x) % mod; // < M } p *= magic[__builtin_ctz(++h)]; } } if(m < n){ rep(i,m){ uint x = a[i].v + mod2 - a[i+m].v; // < 4M a[i].v += a[i+m].v; // < 4M a[i+m].v = x; // < 4M } } const mint in = mint(n).inv(); rep(i,n) a[i] *= in; // < M // finally < mod !! } // A,B = 500000 -> 70ms // verify https://judge.yosupo.jp/submission/44937 V<mint> multiply(V<mint> a, V<mint> b) { int A = si(a), B = si(b); if (!A || !B) return {}; int n = A+B-1; int s = 1; while(s<n) s*=2; if(a == b){ // # of fft call : 3 -> 2 a.resize(s); fft(a); rep(i,s) a[i] *= a[i]; }else{ a.resize(s); fft(a); b.resize(s); fft(b); rep(i,s) a[i] *= b[i]; } invfft(a); a.resize(n); return a; } int main(){ cin.tie(0); ios::sync_with_stdio(false); //DON'T USE scanf/printf/puts !! cout << fixed << setprecision(20); InitFact(1000000); int A,B,C; cin >> A >> B >> C; if((A+B+C)%2){ cout << 0 << endl; return 0; } int n = (A+B+C)/2; auto getf = [&](int A){ V<mint> f(A/2+1); rep(i,A/2+1) f[i] = ifact[i] * ifact[A-2*i]; return f; }; auto fa = getf(A); auto fb = getf(B); auto fc = getf(C); auto f = multiply(multiply(fa,fb),fc); f.resize(n+1); rep(p,n+1) f[p] *= fact[p] * fact[2*n-2*p]; show(f); V<mint> g; // exactly p pair { // g_i = f_i - (n-i,1) f_{i+1} + (n-i,2) f_{i+2} - .. +- f_n V<mint> p(n+1); rep(i,n+1) p[i] = mint(-1).pow(i) * ifact[i]; V<mint> q(n+1); rep(i,n+1) q[i] = ifact[i] * f[n-i]; auto r = multiply(p,q); show(p);show(q);show(r); g.resize(n+1); rep(i,n+1) g[i] = r[n-i] * fact[n-i]; } show(g); mint ans = 0; mint z = 1, w = 0; rep(q,n+1){ int p = n-q; ans += g[p] * Choose(n,p) * z/(z+w+w); mint tmp = z+w; z = w+w, w = tmp; } cout << ans << endl; }