結果
問題 | No.1783 Remix Sum |
ユーザー | sigma425 |
提出日時 | 2021-12-14 08:41:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6,417 ms / 10,000 ms |
コード長 | 13,285 bytes |
コンパイル時間 | 3,148 ms |
コンパイル使用メモリ | 229,212 KB |
実行使用メモリ | 42,884 KB |
最終ジャッジ日時 | 2024-07-23 10:05:01 |
合計ジャッジ時間 | 186,459 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 3 ms
6,940 KB |
testcase_04 | AC | 654 ms
11,332 KB |
testcase_05 | AC | 477 ms
9,804 KB |
testcase_06 | AC | 1,051 ms
14,616 KB |
testcase_07 | AC | 1,189 ms
13,972 KB |
testcase_08 | AC | 581 ms
11,496 KB |
testcase_09 | AC | 660 ms
12,284 KB |
testcase_10 | AC | 484 ms
9,800 KB |
testcase_11 | AC | 383 ms
9,144 KB |
testcase_12 | AC | 1,066 ms
13,064 KB |
testcase_13 | AC | 407 ms
9,280 KB |
testcase_14 | AC | 495 ms
10,720 KB |
testcase_15 | AC | 683 ms
26,668 KB |
testcase_16 | AC | 1,188 ms
13,968 KB |
testcase_17 | AC | 1,327 ms
14,628 KB |
testcase_18 | AC | 390 ms
9,020 KB |
testcase_19 | AC | 989 ms
15,280 KB |
testcase_20 | AC | 545 ms
11,044 KB |
testcase_21 | AC | 981 ms
15,408 KB |
testcase_22 | AC | 896 ms
14,624 KB |
testcase_23 | AC | 926 ms
15,080 KB |
testcase_24 | AC | 312 ms
8,832 KB |
testcase_25 | AC | 976 ms
14,492 KB |
testcase_26 | AC | 1,062 ms
13,188 KB |
testcase_27 | AC | 1,053 ms
15,404 KB |
testcase_28 | AC | 448 ms
9,804 KB |
testcase_29 | AC | 611 ms
11,956 KB |
testcase_30 | AC | 544 ms
11,004 KB |
testcase_31 | AC | 916 ms
14,632 KB |
testcase_32 | AC | 1,510 ms
28,708 KB |
testcase_33 | AC | 618 ms
11,944 KB |
testcase_34 | AC | 320 ms
8,832 KB |
testcase_35 | AC | 415 ms
9,288 KB |
testcase_36 | AC | 418 ms
25,644 KB |
testcase_37 | AC | 420 ms
25,644 KB |
testcase_38 | AC | 418 ms
9,160 KB |
testcase_39 | AC | 332 ms
8,832 KB |
testcase_40 | AC | 374 ms
9,024 KB |
testcase_41 | AC | 318 ms
8,828 KB |
testcase_42 | AC | 323 ms
8,684 KB |
testcase_43 | AC | 413 ms
9,160 KB |
testcase_44 | AC | 4,322 ms
42,620 KB |
testcase_45 | AC | 4,163 ms
42,620 KB |
testcase_46 | AC | 3,818 ms
42,760 KB |
testcase_47 | AC | 3,584 ms
42,428 KB |
testcase_48 | AC | 6,022 ms
42,756 KB |
testcase_49 | AC | 6,417 ms
42,628 KB |
testcase_50 | AC | 4,312 ms
42,748 KB |
testcase_51 | AC | 4,093 ms
42,624 KB |
testcase_52 | AC | 3,785 ms
42,752 KB |
testcase_53 | AC | 3,565 ms
42,428 KB |
testcase_54 | AC | 5,982 ms
42,884 KB |
testcase_55 | AC | 6,351 ms
42,624 KB |
testcase_56 | AC | 4,353 ms
42,620 KB |
testcase_57 | AC | 4,104 ms
42,744 KB |
testcase_58 | AC | 3,806 ms
42,760 KB |
testcase_59 | AC | 3,579 ms
42,300 KB |
testcase_60 | AC | 6,028 ms
42,752 KB |
testcase_61 | AC | 6,393 ms
42,628 KB |
testcase_62 | AC | 4,361 ms
42,616 KB |
testcase_63 | AC | 4,151 ms
42,752 KB |
testcase_64 | AC | 3,787 ms
42,632 KB |
testcase_65 | AC | 3,567 ms
42,428 KB |
testcase_66 | AC | 6,030 ms
42,756 KB |
testcase_67 | AC | 6,405 ms
42,624 KB |
testcase_68 | AC | 3,739 ms
37,932 KB |
testcase_69 | AC | 3,590 ms
38,064 KB |
testcase_70 | AC | 3,331 ms
37,940 KB |
testcase_71 | AC | 3,119 ms
37,608 KB |
testcase_72 | AC | 5,289 ms
38,192 KB |
testcase_73 | AC | 5,690 ms
39,892 KB |
testcase_74 | AC | 3,413 ms
34,944 KB |
testcase_75 | AC | 3,948 ms
41,192 KB |
testcase_76 | AC | 2,723 ms
31,820 KB |
testcase_77 | AC | 633 ms
11,832 KB |
testcase_78 | AC | 1,598 ms
16,324 KB |
testcase_79 | AC | 1,816 ms
29,612 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 push_back #define eb 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> bool chmax(T& x, U y){ if(x<y){ x=y; return true; } return false; } template<class T,class U> bool chmin(T& x, U y){ if(y<x){ x=y; return true; } return false; } 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<class D> D divFloor(D a, D b){ return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0); } template<class D> D divCeil(D a, D b) { return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0); } 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;} template<class T> friend ModInt operator+(T a, const ModInt& b){ return (ModInt(a) += b);} template<class T> friend ModInt operator-(T a, const ModInt& b){ return (ModInt(a) -= b);} template<class T> friend ModInt operator*(T a, const ModInt& b){ return (ModInt(a) *= b);} template<class T> friend ModInt operator/(T a, const ModInt& b){ return (ModInt(a) /= b);} 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<120586241>; // 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. // !!! CHANGE IF MOD is unusual !!! const int ORDER_2_MOD_MINUS_1 = 20; // ord_2 (mod-1) const mint PRIMITIVE_ROOT = 6; // primitive root of (Z/pZ)* void fft(V<mint>& a){ static constexpr uint mod = mint::mod; static constexpr uint mod2 = mod + mod; static const int H = ORDER_2_MOD_MINUS_1; static const mint root = PRIMITIVE_ROOT; 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 = ORDER_2_MOD_MINUS_1; static const mint root = PRIMITIVE_ROOT; 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 !! } /* h[i1+j1][i2+j2]..[ik+jk] += f[i1][i2]..[ik] * g[i1][i2]..[ik] をする ただし 添字の範囲は 0 <= ip,jp < np で、足した結果一箇所でもはみ出た値は捨てる f,g は flatten されている (i1,i2,..,ik) が i1 + i2n1 + i3n1n2 + .. に対応する magicはcalc_magicで計算したのを使う O(knlogn) 各次元を2倍にして愚直にやるとO(2^k nlogn) とかになるはずで、すげ~ */ V<int> calc_magic(const vector<int>& ns){ int k = si(ns); if(k == 0) return {}; int n = 1; for(int ni: ns) n *= ni; V<int> magic(n); rep(i,n){ int x = i; rep(j,k){ magic[i] += x; x /= ns[j]; } magic[i] %= k; } return magic; } vector<mint> multivariate_mult(const vector<mint>& f, const vector<mint>& g, const vector<int>& ns, const vector<int>& magic){ assert(si(f) == si(g)); int n = si(f); int k = si(ns); if(k == 0){ return {f[0]*g[0]}; } int s = 1; while(s<n*2-1) s*=2; vector<mint> h(n); vector<vector<mint>> zf(k,vector<mint>(s)); vector<vector<mint>> zg(k,vector<mint>(s)); vector<vector<mint>> zh(k,vector<mint>(s)); rep(i,n) zf[magic[i]][i] = f[i]; rep(i,k) fft(zf[i]); rep(i,n) zg[magic[i]][i] = g[i]; rep(i,k) fft(zg[i]); rep(a,k) rep(b,k){ int c = (a+b)%k; rep(i,s) zh[c][i] += zf[a][i] * zg[b][i]; } rep(i,k) invfft(zh[i]); rep(i,n) h[i] = zh[magic[i]][i]; return h; } vector<mint> multivariate_log(const vector<mint>& f, const vector<int>& ns, const vector<int>& magic){ exit(1); } V<int> tens = {1,10,100,1000,10000,100000}; V<mint> zs; vector<mint> mult(vector<mint> f, vector<mint> g, int A,int B, bool za, bool zb, bool zc){ int n = si(f); auto zeta10 = [&](V<mint> f){ V<mint> g(10); rep(i,10) rep(j,10) g[i] += f[j] * zs[i*j]; return g; }; auto izeta10 = [&](V<mint> f){ const static mint i10 = mint(10).inv(); V<mint> g(10); rep(i,10) rep(j,10) g[i] += f[j] * zs[90-i*j] * i10; return g; }; auto zeta = [&](vector<mint> f){ for(int d=A;d<A+B;d++){ // cyclic DFTed dim rep(s,n) if(s/tens[d]%10 == 0){ V<mint> buf(10); rep(i,10) buf[i] = f[s+tens[d]*i]; buf = zeta10(buf); rep(i,10) f[s+tens[d]*i] = buf[i]; } } return f; }; auto izeta = [&](vector<mint> f){ for(int d=A;d<A+B;d++){ // cyclic DFTed dim rep(s,n) if(s/tens[d]%10 == 0){ V<mint> buf(10); rep(i,10) buf[i] = f[s+tens[d]*i]; buf = izeta10(buf); rep(i,10) f[s+tens[d]*i] = buf[i]; } } return f; }; if(!za) f = zeta(f); if(!zb) g = zeta(g); V<mint> zf(tens[A]), zg(tens[A]),zh; V<int> ns(A,10); V<int> magic = calc_magic(ns); rep(s,si(f)) if(s%tens[A] == 0){ rep(i,tens[A]) zf[i] = f[s+i], zg[i] = g[s+i]; zh = multivariate_mult(zf,zg,ns,magic); // show(zf);show(zg);show(zh); // show(ns);show(magic); // show("------------"); rep(i,tens[A]) f[s+i] = zh[i]; } if(!zc) f = izeta(f); return f; } template <class T, class Op = multiplies<>> constexpr T power(T a, uint64_t n, T init = 1, Op op = Op{}) { while (n) { if (n & 1) init = op(init, a); if (n >>= 1) a = op(a, a); } return init; } int main(){ cin.tie(0); ios::sync_with_stdio(false); //DON'T USE scanf/printf/puts !! cout << fixed << setprecision(20); int N,A,B; ll X; { int K; cin >> N; cin >> K; cin >> X; int T; cin >> T; A = T, B = K-T; } { mint z = mint(6).pow((mint::mod-1)/10); rep(i,91) zs.pb(z.pow(i)); } V<mint> f(TEN(A+B)); while(N--){ int x; cin >> x; f[x]++; } auto mul = [&](auto x,auto y,bool za,bool zb,bool zc){ return mult(x,y,A,B,za,zb,zc); }; V<mint> id(TEN(A+B)); id[0] = 1; // f = power(f,X,id,mul); // for(auto v: f) cout << v << endl; V<mint> f0(TEN(A+B)),f1(TEN(A+B)); rep(s,TEN(A+B)){ if(s%TEN(A) == 0) f0[s] = f[s]; else f1[s] = f[s]; } ll XX = max(X-45,0LL); ll work = X-XX; VV<mint> f1pow(work+1); f1pow[0] = id; rep1(i,work) f1pow[i] = mul(f1pow[i-1], f1, 0,0,0); int n = si(f); auto zeta10 = [&](V<mint> f){ V<mint> g(10); rep(i,10) rep(j,10) g[i] += f[j] * zs[i*j]; return g; }; auto izeta10 = [&](V<mint> f){ const static mint i10 = mint(10).inv(); V<mint> g(10); rep(i,10) rep(j,10) g[i] += f[j] * zs[90-i*j] * i10; return g; }; auto zeta = [&](vector<mint> f){ for(int d=A;d<A+B;d++){ // cyclic DFTed dim rep(s,n) if(s/tens[d]%10 == 0){ V<mint> buf(10); rep(i,10) buf[i] = f[s+tens[d]*i]; buf = zeta10(buf); rep(i,10) f[s+tens[d]*i] = buf[i]; } } return f; }; auto izeta = [&](vector<mint> f){ for(int d=A;d<A+B;d++){ // cyclic DFTed dim rep(s,n) if(s/tens[d]%10 == 0){ V<mint> buf(10); rep(i,10) buf[i] = f[s+tens[d]*i]; buf = izeta10(buf); rep(i,10) f[s+tens[d]*i] = buf[i]; } } return f; }; show(f0); show(f1); show(f1pow); show(XX); VV<mint> gs(work+1); if(true){ auto g0 = zeta(f0); V<mint> g(TEN(A+B)); rep(s,n) if(s%TEN(A) == 0) g[s] = g0[s].pow(XX); rep(i,work+1){ gs[work-i] = g; rep(s,n) g[s] *= g0[s]; } } show(gs); V<mint> ans(TEN(A+B)); mint choose = 1; rep(i,work+1){ // auto p = mul(f1pow[i],gs[i],0,1,1); V<mint> p; if(true){ auto F = zeta(f1pow[i]); auto G = gs[i]; show(F);show(G); rep(s,si(F)) if(s%tens[A] == 0){ rep(i,tens[A]) F[s+i] *= G[s]; } p = F; } rep(s,n) ans[s] += p[s] * choose; choose *= X-i; choose /= i+1; } ans = izeta(ans); rep(s,n) cout << ans[s] << endl; }