結果
問題 | No.1261 数字集め |
ユーザー | beet |
提出日時 | 2020-10-16 22:35:51 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,419 ms / 8,000 ms |
コード長 | 4,457 bytes |
コンパイル時間 | 2,478 ms |
コンパイル使用メモリ | 210,824 KB |
実行使用メモリ | 270,172 KB |
最終ジャッジ日時 | 2023-09-28 09:26:48 |
合計ジャッジ時間 | 152,441 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,419 ms
269,396 KB |
testcase_01 | AC | 682 ms
137,648 KB |
testcase_02 | AC | 1,543 ms
212,544 KB |
testcase_03 | AC | 1,562 ms
214,492 KB |
testcase_04 | AC | 946 ms
162,348 KB |
testcase_05 | AC | 2,159 ms
261,484 KB |
testcase_06 | AC | 1,093 ms
175,100 KB |
testcase_07 | AC | 1,610 ms
219,556 KB |
testcase_08 | AC | 848 ms
152,808 KB |
testcase_09 | AC | 1,137 ms
179,196 KB |
testcase_10 | AC | 94 ms
77,560 KB |
testcase_11 | AC | 2,124 ms
258,700 KB |
testcase_12 | AC | 1,874 ms
238,520 KB |
testcase_13 | AC | 1,637 ms
221,864 KB |
testcase_14 | AC | 144 ms
87,804 KB |
testcase_15 | AC | 733 ms
143,556 KB |
testcase_16 | AC | 1,640 ms
219,904 KB |
testcase_17 | AC | 1,278 ms
190,556 KB |
testcase_18 | AC | 751 ms
144,904 KB |
testcase_19 | AC | 1,558 ms
215,264 KB |
testcase_20 | AC | 163 ms
91,392 KB |
testcase_21 | AC | 2,220 ms
269,940 KB |
testcase_22 | AC | 2,179 ms
269,924 KB |
testcase_23 | AC | 2,226 ms
270,000 KB |
testcase_24 | AC | 2,225 ms
270,172 KB |
testcase_25 | AC | 2,224 ms
270,044 KB |
testcase_26 | AC | 2,251 ms
270,036 KB |
testcase_27 | AC | 2,275 ms
269,980 KB |
testcase_28 | AC | 2,183 ms
269,924 KB |
testcase_29 | AC | 2,223 ms
270,036 KB |
testcase_30 | AC | 2,197 ms
270,028 KB |
testcase_31 | AC | 2,225 ms
270,024 KB |
testcase_32 | AC | 2,228 ms
269,828 KB |
testcase_33 | AC | 2,263 ms
269,996 KB |
testcase_34 | AC | 2,192 ms
270,036 KB |
testcase_35 | AC | 2,177 ms
269,992 KB |
testcase_36 | AC | 2,229 ms
270,032 KB |
testcase_37 | AC | 2,219 ms
270,040 KB |
testcase_38 | AC | 2,242 ms
270,160 KB |
testcase_39 | AC | 2,280 ms
270,040 KB |
testcase_40 | AC | 2,257 ms
269,868 KB |
testcase_41 | AC | 2,249 ms
270,048 KB |
testcase_42 | AC | 2,275 ms
270,004 KB |
testcase_43 | AC | 2,286 ms
270,036 KB |
testcase_44 | AC | 2,046 ms
245,920 KB |
testcase_45 | AC | 357 ms
109,428 KB |
testcase_46 | AC | 1,038 ms
165,188 KB |
testcase_47 | AC | 681 ms
136,116 KB |
testcase_48 | AC | 1,598 ms
217,124 KB |
testcase_49 | AC | 1,877 ms
244,108 KB |
testcase_50 | AC | 1,692 ms
225,224 KB |
testcase_51 | AC | 396 ms
114,620 KB |
testcase_52 | AC | 90 ms
76,044 KB |
testcase_53 | AC | 405 ms
114,904 KB |
testcase_54 | AC | 481 ms
120,672 KB |
testcase_55 | AC | 197 ms
95,224 KB |
testcase_56 | AC | 259 ms
101,336 KB |
testcase_57 | AC | 1,522 ms
209,316 KB |
testcase_58 | AC | 349 ms
110,380 KB |
testcase_59 | AC | 1,975 ms
248,920 KB |
testcase_60 | AC | 419 ms
119,320 KB |
testcase_61 | AC | 689 ms
138,952 KB |
testcase_62 | AC | 1,770 ms
229,972 KB |
testcase_63 | AC | 226 ms
98,636 KB |
testcase_64 | AC | 2,189 ms
262,896 KB |
testcase_65 | AC | 1,353 ms
196,668 KB |
testcase_66 | AC | 1,102 ms
175,572 KB |
testcase_67 | AC | 1,757 ms
231,680 KB |
testcase_68 | AC | 1,030 ms
170,060 KB |
testcase_69 | AC | 987 ms
167,836 KB |
testcase_70 | AC | 774 ms
147,080 KB |
testcase_71 | AC | 1,631 ms
222,760 KB |
testcase_72 | AC | 519 ms
125,516 KB |
testcase_73 | AC | 622 ms
134,548 KB |
testcase_74 | AC | 274 ms
101,828 KB |
testcase_75 | AC | 920 ms
161,560 KB |
testcase_76 | AC | 1,479 ms
209,596 KB |
testcase_77 | AC | 1,759 ms
233,000 KB |
testcase_78 | AC | 84 ms
73,860 KB |
testcase_79 | AC | 1,809 ms
239,268 KB |
testcase_80 | AC | 92 ms
75,836 KB |
testcase_81 | AC | 148 ms
88,816 KB |
testcase_82 | AC | 1,376 ms
201,568 KB |
testcase_83 | AC | 568 ms
128,656 KB |
testcase_84 | AC | 2,238 ms
269,988 KB |
testcase_85 | AC | 2,197 ms
269,920 KB |
testcase_86 | AC | 2,201 ms
270,040 KB |
testcase_87 | AC | 2,209 ms
269,952 KB |
testcase_88 | AC | 2,237 ms
270,040 KB |
testcase_89 | AC | 2,232 ms
270,036 KB |
testcase_90 | AC | 2,247 ms
269,884 KB |
testcase_91 | AC | 2,227 ms
270,000 KB |
testcase_92 | AC | 2,230 ms
269,992 KB |
testcase_93 | AC | 2,254 ms
270,004 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using Int = long long; const char newl = '\n'; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);} template<typename T=Int> vector<T> read(size_t n){ vector<T> ts(n); for(size_t i=0;i<n;i++) cin>>ts[i]; return ts; } template<typename T,T MOD = 1000000007> struct Mint{ static constexpr T mod = MOD; T v; Mint():v(0){} Mint(signed v):v(v){} Mint(long long t){v=t%MOD;if(v<0) v+=MOD;} Mint pow(long long k){ Mint res(1),tmp(v); while(k){ if(k&1) res*=tmp; tmp*=tmp; k>>=1; } return res; } static Mint add_identity(){return Mint(0);} static Mint mul_identity(){return Mint(1);} Mint inv(){return pow(MOD-2);} Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;} Mint& operator/=(Mint a){return (*this)*=a.inv();} Mint operator+(Mint a) const{return Mint(v)+=a;} Mint operator-(Mint a) const{return Mint(v)-=a;} Mint operator*(Mint a) const{return Mint(v)*=a;} Mint operator/(Mint a) const{return Mint(v)/=a;} Mint operator-() const{return v?Mint(MOD-v):Mint(v);} bool operator==(const Mint a)const{return v==a.v;} bool operator!=(const Mint a)const{return v!=a.v;} bool operator <(const Mint a)const{return v <a.v;} static Mint comb(long long n,Int k){ Mint num(1),dom(1); for(Int i=0;i<k;i++){ num*=Mint(n-i); dom*=Mint(i+1); } return num/dom; } }; template<typename T,T MOD> constexpr T Mint<T, MOD>::mod; template<typename T,T MOD> ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;} template<typename M_> class Enumeration{ using M = M_; protected: static vector<M> fact,finv,invs; public: static void init(Int n){ n=min<decltype(M::mod)>(n,M::mod-1); Int m=fact.size(); if(n<m) return; fact.resize(n+1,1); finv.resize(n+1,1); invs.resize(n+1,1); if(m==0) m=1; for(Int i=m;i<=n;i++) fact[i]=fact[i-1]*M(i); finv[n]=M(1)/fact[n]; for(Int i=n;i>=m;i--) finv[i-1]=finv[i]*M(i); for(Int i=m;i<=n;i++) invs[i]=finv[i]*fact[i-1]; } static M Fact(Int n){ init(n); return fact[n]; } static M Finv(Int n){ init(n); return finv[n]; } static M Invs(Int n){ init(n); return invs[n]; } static M C(Int n,Int k){ if(n<k||k<0) return M(0); init(n); return fact[n]*finv[n-k]*finv[k]; } static M P(Int n,Int k){ if(n<k||k<0) return M(0); init(n); return fact[n]*finv[n-k]; } // put n identical balls into k distinct boxes static M H(Int n,Int k){ if(n<0||k<0) return M(0); if(!n&&!k) return M(1); init(n+k); return C(n+k-1,n); } }; template<typename M> vector<M> Enumeration<M>::fact=vector<M>(); template<typename M> vector<M> Enumeration<M>::finv=vector<M>(); template<typename M> vector<M> Enumeration<M>::invs=vector<M>(); //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); Int n,m; cin>>n>>m; vector<Int> as(n+1); for(Int i=2;i<=n;i++) cin>>as[i]; for(Int &a:as) a--; using M = Mint<Int>; using E = Enumeration<M>; E::init(3e6); M ans{0}; vector<Int> toN(n+1,0); vector<vector<Int>> G(n+1); vector<M> po(n+1); for(Int i=2;i<=n;i++) po[i]=M(as[i]).pow(m-1); auto inv=[&](Int d){return d<0?-E::Invs(-d):E::Invs(d);}; auto calc=[&](Int i,Int j){ assert(i!=j); assert(1<min(i,j)); assert(max(i,j)<n); Int x=as[i],y=as[j],z=as[n]; M res{0}; res+=po[i]*M(y); res-=po[i]*M(z); res+=po[n]*M(x); res-=po[j]*M(x); res+=po[j]*M(z); res-=po[n]*M(y); res*=inv(x-y); res*=inv(x-z); res*=inv(y-z); return res; }; auto enable=[&](Int i){ assert(!toN[i]); toN[i]=1; for(Int j:G[i]) ans+=calc(j,i); G[i].clear(); }; for(Int i=2;i<=n;i++) for(Int j=i+i;j<=n;j+=i) G[j].emplace_back(i); for(Int i=2;i<n;i++) if(n%i==0) enable(i); cout<<ans<<endl; Int q; cin>>q; for(Int i=0;i<q;i++){ Int x,y; cin>>x>>y; if(y==n){ enable(x); }else{ if(!toN[y]) G[y].emplace_back(x); else ans+=calc(x,y); } cout<<ans<<newl; } return 0; }