結果
問題 | No.2770 Coupon Optimization |
ユーザー |
|
提出日時 | 2024-05-31 22:04:50 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 788 ms / 3,000 ms |
コード長 | 11,888 bytes |
コンパイル時間 | 3,477 ms |
コンパイル使用メモリ | 230,260 KB |
実行使用メモリ | 30,504 KB |
最終ジャッジ日時 | 2024-12-20 23:34:11 |
合計ジャッジ時間 | 14,526 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;long long mod = 998244353;//入力が必ずmod未満の時に使う.struct mint{long long v = 0;mint(){} mint(int a){v = a;} mint(long long a){v = a;} mint(unsigned long long a){v = a;}long long val(){return v;}void modu(){v %= mod;}mint repeat2mint(const long long a,long long b){mint ret = 1,p = a;while(b){if(b&1) ret *= p;p *= p; b >>= 1;}return ret;};mint operator+(const mint b){return mint(v)+=b;}mint operator-(const mint b){return mint(v)-=b;}mint operator*(const mint b){return mint(v)*=b;}mint operator/(const mint b){return mint(v)/=b;}mint operator+=(const mint b){v += b.v; if(v >= mod) v -= mod;return *this;}mint operator-=(const mint b){v -= b.v; if(v < 0) v += mod;return *this;}mint operator*=(const mint b){v = v*b.v%mod; return *this;}mint operator/=(mint b){if(b == 0) assert(false);int left = mod-2;while(left){if(left&1) *this *= b; b *= b; left >>= 1;}return *this;}mint operator++(int){*this += 1; return *this;}mint operator--(int){*this -= 1; return *this;}bool operator==(const mint b){return v == b.v;}bool operator!=(const mint b){return v != b.v;}bool operator>(const mint b){return v > b.v;}bool operator>=(const mint b){return v >= b.v;}bool operator<(const mint b){return v < b.v;}bool operator<=(const mint b){return v <= b.v;}mint pow(const long long x){return repeat2mint(v,x);}mint inv(){return mint(1)/v;}};namespace to_fold{ //纏めて折り畳むためのやつ 苦労したが結局ほぼACLの写経.__int128_t safemod(__int128_t a,long long m){a %= m; if(a < 0) a += m; return a;}pair<long long,long long> invgcd(long long a,long long b){//return {gcd(a,b),x} (xa≡g(mod b))a = safemod(a,b);if(a == 0) return {b,0};long long x = 0,y = 1,memob = b;while(a){long long q = b/a;b -= a*q;swap(x,y); y -= q*x;swap(a,b);}if(x < 0) x += memob/b;return {b,x};}long long Garner(vector<long long> &A,vector<long long> &M){__int128_t mulM = 1,x = A.at(0)%M.at(0); //Mの要素のペア互いに素必須.for(int i=1; i<A.size(); i++){//assert(gcd(mulM,M.at(i-1)) == 1);mulM *= M.at(i-1); //2乗がオーバーフローする時__int128_tlong long t = safemod((A.at(i)-x)*invgcd(mulM,M.at(i)).second,M.at(i));x += t*mulM;}return x%mod;}int countzero(unsigned long long x){if(x == 0) return 64;else return __popcount((x&-x)-1);}struct fftinfo{vector<mint> root,iroot,rate2,irate2,rate3,irate3;fftinfo(mint g){int rank2 = countzero(mod-1);root.resize(rank2+1),iroot = root;rate2.resize(max(0,rank2-2+1)); irate2 = rate2;rate3.resize(max(0,rank2-3+1)); irate3 = rate3;root[rank2] = g.pow((mod-1)>>rank2);iroot[rank2] = root[rank2].inv();for(int i=rank2-1; i>=0; i--){root[i] = root[i+1]*root[i+1];iroot[i] = iroot[i+1]*iroot[i+1];}mint mul = 1,imul = 1;for(int i=0; i<=rank2-2; i++){rate2[i] = root[i+2]*mul;irate2[i] = iroot[i+2]*imul;mul *= iroot[i+2],imul *= root[i+2];}mul = 1,imul = 1;for(int i=0; i<=rank2-3; i++){rate3[i] = root[i+3]*mul;irate3[i] = iroot[i+3]*imul;mul *= iroot[i+3],imul *= root[i+3];}}};mint findroot(){if(mod == 998244353) return mint(3);else if(mod == 754974721) return mint(11);else if(mod == 167772161) return mint(3);else if(mod == 469762049) return mint(3);long long p = mod-1;vector<long long> P;for(long long i=2; i*i<=p; i++){if(p%i) continue;while(p%i == 0) p /= i;P.push_back(i);}if(p != 1) P.push_back(p);p = mod-1;random_device rnd; mt19937 mt(rnd());while(true){mint ret = mt()%mod;if(ret == 1 || ret == 0) continue;if(ret.pow(p) != 1) continue;bool ok = true;for(auto check : P) if(ret.pow(p/check) == 1){ok = false; break;}if(ok) return ret;} //O(√P)らしいです.}void NTT(vector<mint> &A,fftinfo &info){int N = A.size(),ln = countzero(N);int dep = 0;while(dep < ln){if(ln-dep == 1){int p = 1<<(ln-dep-1);mint rot = 1;for(int o=0; o<(1<<dep); o++){int offset = o<<(ln-dep);for(int i=0; i<p; i++){mint l = A.at(i+offset),r = A.at(i+offset+p)*rot;A.at(i+offset) = l+r; A.at(i+offset+p) = l-r;}if(o+1 != (1<<dep)) rot *= info.rate2[countzero(~(unsigned int)o)];}dep++;}else{int p = 1<<(ln-dep-2);mint rot = 1,imag = info.root[2];for(int o=0; o<(1<<dep); o++){mint rot2 = rot*rot,rot3 = rot2*rot;int offset = o<<(ln-dep);for(int i=0; i<p; i++){auto mod2 = 1ULL*mod*mod;auto a0 = 1ULL*A.at(i+offset).v;auto a1 = 1ULL*A.at(i+offset+p).v*rot.v;auto a2 = 1ULL*A.at(i+offset+p+p).v*rot2.v;auto a3 = 1ULL*A.at(i+offset+p+p+p).v*rot3.v;auto a1m2a3im = 1ULL*(a1+mod2-a3+mod)%mod*imag.v;auto m2a2 = mod2-a2;A.at(i+offset) = (long long)((a0+a2+a1+a3)%mod);A.at(i+offset+p) = (long long)((a0+a2+(2*mod2-(a1+a3)))%mod);A.at(i+offset+p+p) = (long long)((a0+m2a2+a1m2a3im)%mod);A.at(i+offset+p+p+p) = (long long)((a0+m2a2+(mod2-a1m2a3im))%mod);}if(o+1 != (1<<dep)) rot *= info.rate3[countzero(~(unsigned int)o)];}dep += 2;}}}void INTT(vector<mint> &A,fftinfo &info){int N = A.size(),ln = countzero(N);int dep = ln;while(dep){if(dep == 1){int p = 1<<(ln-dep);mint irot = 1;for(int o=0; o<(1<<(dep-1)); o++){int offset = o<<(ln-dep+1);for(int i=0; i<p; i++){mint l = A.at(i+offset),r = A.at(i+offset+p);A.at(i+offset) = l+r;A.at(i+offset+p) = (long long)((unsigned long long)((mod+l.v-r.v)*irot.v)%mod);}if(o+1 != (1<<(dep-1))) irot *= info.irate2[countzero(~(unsigned int)o)];}dep--;}else{int p = 1<<(ln-dep);mint irot = 1,iimag = info.iroot[2];for(int o=0; o<(1<<(dep-2)); o++){mint irot2 = irot*irot,irot3 = irot2*irot;int offset = o<<(ln-dep+2);for(int i=0; i<p; i++){auto a0 = 1ULL*A.at(i+offset).v,a1 = 1ULL*A.at(i+offset+p).v;auto a2 = 1ULL*A.at(i+offset+p+p).v,a3 = 1ULL*A.at(i+offset+p+p+p).v;auto gotyagotya = 1ULL*((mod+a2-a3)*iimag.v%mod);A.at(i+offset) = (long long)((a0+a1+a2+a3)%mod);A.at(i+offset+p) = (long long)((a0+(mod-a1)+gotyagotya)*irot.v%mod);A.at(i+offset+p+p) = (long long)((a0+a1+(mod-a2)+(mod-a3))*irot2.v%mod);A.at(i+offset+p+p+p) = (long long)((a0+(mod-a1)+(mod-gotyagotya))*irot3.v%mod);}if(o+1 != (1<<(dep-2))) irot *= info.irate3[countzero(~(unsigned int)o)];}dep -= 2;}}}vector<mint> convolutionnaive(vector<mint> &A,vector<mint> &B){vector<mint> ret(A.size()+B.size()-1);for(int i=0; i<A.size(); i++) for(int k=0; k<B.size(); k++) ret.at(i+k) += A.at(i)*B.at(k);return ret;}vector<mint> convolution(vector<mint> &A,vector<mint> &B){int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1,N = 1;if(siza == 0 || sizb == 0) return {};while(N <= sizc) N <<= 1;vector<mint> ca = A,cb = B;ca.resize(N),cb.resize(N);if(min(siza,sizb) <= 40) return convolutionnaive(A,B);assert((mod-1)%N == 0);mint root = findroot();fftinfo info(root);NTT(ca,info); NTT(cb,info);for(int i=0; i<N; i++) ca.at(i) *= cb.at(i);INTT(ca,info); ca.resize(sizc);mint divN = mint(N).inv();for(int i=0; i<sizc; i++) ca.at(i) *= divN;return ca;}vector<long long> convolution_ll(vector<long long> &A,vector<long long> &B){int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;if(siza == 0 || sizb == 0) return {};unsigned long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049;unsigned long long m1m2 = mod1*mod2,m2m3 = mod2*mod3,m3m1 = mod3*mod1,m1m2m3 = mod1*mod2*mod3;unsigned long long i1 = invgcd(m2m3,mod1).second,i2 = invgcd(m3m1,mod2).second,i3 = invgcd(m1m2,mod3).second;assert(sizc <= (1<<24));mod = mod1;vector<mint> a(siza),b(sizb);for(int i=0; i<siza; i++) a.at(i) = A.at(i)%mod;for(int i=0; i<sizb; i++) b.at(i) = B.at(i)%mod;vector<mint> C1 = convolution(a,b);mod = mod2;for(int i=0; i<siza; i++) a.at(i) = A.at(i)%mod;for(int i=0; i<sizb; i++) b.at(i) = B.at(i)%mod;vector<mint> C2 = convolution(a,b);mod = mod3;for(int i=0; i<siza; i++) a.at(i) = A.at(i)%mod;for(int i=0; i<sizb; i++) b.at(i) = B.at(i)%mod;vector<mint> C3 = convolution(a,b);vector<long long> ret(sizc);vector<unsigned long long> offset = {0,0,m1m2m3,2*m1m2m3,3*m1m2m3};for(int i=0; i<sizc; i++){unsigned long long x = 0;x += (C1.at(i).v*i1)%mod1*m2m3;x += (C2.at(i).v*i2)%mod2*m3m1;x += (C3.at(i).v*i3)%mod3*m1m2;long long diff = C1.at(i).v-((long long)x+(long long)mod1)%mod1;if(diff < 0) diff += mod1;x -= offset.at(diff%5);ret.at(i) = x;}return ret;}vector<mint> convolution_llmod(vector<mint> &A,vector<mint> &B,long long memomod){int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;if(siza == 0 || sizb == 0) return {};long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049;assert(sizc <= (1<<24));mod = mod1;vector<mint> a(siza),b(sizb);for(int i=0; i<siza; i++) a.at(i) = A.at(i).v%mod;for(int i=0; i<sizb; i++) b.at(i) = B.at(i).v%mod;vector<mint> C1 = convolution(a,b);mod = mod2;for(int i=0; i<siza; i++) a.at(i) = A.at(i).v%mod;for(int i=0; i<sizb; i++) b.at(i) = B.at(i).v%mod;vector<mint> C2 = convolution(a,b);mod = mod3;for(int i=0; i<siza; i++) a.at(i) = A.at(i).v%mod;for(int i=0; i<sizb; i++) b.at(i) = B.at(i).v%mod;vector<mint> C3 = convolution(a,b);mod = memomod;vector<mint> ret(sizc);for(int i=0; i<sizc; i++){vector<long long> A = {C1.at(i).v,C2.at(i).v,C3.at(i).v};vector<long long> M = {mod1,mod2,mod3};ret.at(i) = Garner(A,M);}return ret;}}using namespace to_fold;int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);int N,M; cin >> N >> M;vector<long long> A(N),B(M);for(auto &a : A) cin >> a,a /= 100;for(auto &b : B) cin >> b;sort(A.begin(),A.end());sort(B.rbegin(),B.rend());while(B.size() < N) B.push_back(0);while(B.size() > N) B.pop_back();vector<long long> C = convolution_ll(A,B);long long answer = 0;for(int i=0; i<N; i++){answer += A.at(i)*100;cout << answer-C.at(i) << "\n";}}