結果
問題 | No.1261 数字集め |
ユーザー | maroon_kuri |
提出日時 | 2020-10-16 22:29:26 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,973 ms / 8,000 ms |
コード長 | 12,352 bytes |
コンパイル時間 | 3,309 ms |
コンパイル使用メモリ | 213,756 KB |
実行使用メモリ | 140,528 KB |
最終ジャッジ日時 | 2023-09-28 09:23:23 |
合計ジャッジ時間 | 108,292 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,973 ms
140,156 KB |
testcase_01 | AC | 327 ms
65,032 KB |
testcase_02 | AC | 1,012 ms
107,776 KB |
testcase_03 | AC | 1,008 ms
108,940 KB |
testcase_04 | AC | 540 ms
78,868 KB |
testcase_05 | AC | 1,472 ms
135,468 KB |
testcase_06 | AC | 600 ms
86,160 KB |
testcase_07 | AC | 1,050 ms
111,532 KB |
testcase_08 | AC | 415 ms
73,516 KB |
testcase_09 | AC | 661 ms
88,264 KB |
testcase_10 | AC | 17 ms
30,136 KB |
testcase_11 | AC | 1,408 ms
133,728 KB |
testcase_12 | AC | 1,261 ms
122,612 KB |
testcase_13 | AC | 1,089 ms
112,816 KB |
testcase_14 | AC | 41 ms
36,040 KB |
testcase_15 | AC | 450 ms
68,264 KB |
testcase_16 | AC | 1,041 ms
111,864 KB |
testcase_17 | AC | 749 ms
95,160 KB |
testcase_18 | AC | 376 ms
69,108 KB |
testcase_19 | AC | 1,119 ms
109,276 KB |
testcase_20 | AC | 58 ms
38,056 KB |
testcase_21 | AC | 1,610 ms
140,344 KB |
testcase_22 | AC | 1,600 ms
140,384 KB |
testcase_23 | AC | 1,620 ms
140,476 KB |
testcase_24 | AC | 1,541 ms
140,448 KB |
testcase_25 | AC | 1,589 ms
140,412 KB |
testcase_26 | AC | 1,618 ms
140,400 KB |
testcase_27 | AC | 1,620 ms
140,452 KB |
testcase_28 | AC | 1,554 ms
140,444 KB |
testcase_29 | AC | 1,550 ms
140,340 KB |
testcase_30 | AC | 1,586 ms
140,384 KB |
testcase_31 | AC | 1,622 ms
140,512 KB |
testcase_32 | AC | 1,567 ms
140,528 KB |
testcase_33 | AC | 1,563 ms
140,412 KB |
testcase_34 | AC | 1,535 ms
140,404 KB |
testcase_35 | AC | 1,595 ms
140,348 KB |
testcase_36 | AC | 1,592 ms
140,388 KB |
testcase_37 | AC | 1,553 ms
140,464 KB |
testcase_38 | AC | 1,567 ms
140,352 KB |
testcase_39 | AC | 1,651 ms
140,452 KB |
testcase_40 | AC | 1,633 ms
140,412 KB |
testcase_41 | AC | 1,568 ms
140,408 KB |
testcase_42 | AC | 1,541 ms
140,388 KB |
testcase_43 | AC | 1,723 ms
140,432 KB |
testcase_44 | AC | 1,675 ms
126,576 KB |
testcase_45 | AC | 210 ms
48,608 KB |
testcase_46 | AC | 542 ms
80,668 KB |
testcase_47 | AC | 369 ms
63,836 KB |
testcase_48 | AC | 1,044 ms
110,164 KB |
testcase_49 | AC | 1,294 ms
125,600 KB |
testcase_50 | AC | 1,185 ms
114,656 KB |
testcase_51 | AC | 186 ms
51,668 KB |
testcase_52 | AC | 34 ms
29,356 KB |
testcase_53 | AC | 222 ms
51,620 KB |
testcase_54 | AC | 275 ms
54,976 KB |
testcase_55 | AC | 99 ms
40,264 KB |
testcase_56 | AC | 167 ms
43,856 KB |
testcase_57 | AC | 1,072 ms
105,720 KB |
testcase_58 | AC | 189 ms
49,064 KB |
testcase_59 | AC | 1,395 ms
128,360 KB |
testcase_60 | AC | 241 ms
54,076 KB |
testcase_61 | AC | 349 ms
65,460 KB |
testcase_62 | AC | 1,211 ms
117,584 KB |
testcase_63 | AC | 90 ms
42,268 KB |
testcase_64 | AC | 1,577 ms
136,196 KB |
testcase_65 | AC | 856 ms
98,468 KB |
testcase_66 | AC | 737 ms
86,736 KB |
testcase_67 | AC | 1,184 ms
118,508 KB |
testcase_68 | AC | 593 ms
83,288 KB |
testcase_69 | AC | 576 ms
81,900 KB |
testcase_70 | AC | 445 ms
70,128 KB |
testcase_71 | AC | 1,118 ms
113,432 KB |
testcase_72 | AC | 256 ms
57,880 KB |
testcase_73 | AC | 335 ms
63,084 KB |
testcase_74 | AC | 130 ms
44,444 KB |
testcase_75 | AC | 607 ms
78,428 KB |
testcase_76 | AC | 1,044 ms
106,288 KB |
testcase_77 | AC | 1,260 ms
119,136 KB |
testcase_78 | AC | 33 ms
28,248 KB |
testcase_79 | AC | 1,276 ms
122,980 KB |
testcase_80 | AC | 56 ms
29,052 KB |
testcase_81 | AC | 75 ms
36,828 KB |
testcase_82 | AC | 902 ms
101,296 KB |
testcase_83 | AC | 322 ms
59,780 KB |
testcase_84 | AC | 1,659 ms
140,492 KB |
testcase_85 | AC | 1,663 ms
140,360 KB |
testcase_86 | AC | 1,648 ms
140,360 KB |
testcase_87 | AC | 1,630 ms
140,424 KB |
testcase_88 | AC | 1,656 ms
140,428 KB |
testcase_89 | AC | 1,678 ms
140,408 KB |
testcase_90 | AC | 1,620 ms
140,300 KB |
testcase_91 | AC | 1,610 ms
140,412 KB |
testcase_92 | AC | 1,640 ms
140,492 KB |
testcase_93 | AC | 1,708 ms
140,348 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; //fast IO by yosupo struct Scanner { FILE* fp = nullptr; char line[(1 << 15) + 1]; size_t st = 0, ed = 0; void reread() { memmove(line, line + st, ed - st); ed -= st; st = 0; ed += fread(line + ed, 1, (1 << 15) - ed, fp); line[ed] = '\0'; } bool succ() { while (true) { if (st == ed) { reread(); if (st == ed) return false; } while (st != ed && isspace(line[st])) st++; if (st != ed) break; } if (ed - st <= 50) reread(); return true; } template <class T, enable_if_t<is_same<T, string>::value, int> = 0> bool read_single(T& ref) { if (!succ()) return false; while (true) { size_t sz = 0; while (st + sz < ed && !isspace(line[st + sz])) sz++; ref.append(line + st, sz); st += sz; if (!sz || st != ed) break; reread(); } return true; } template <class T, enable_if_t<is_integral<T>::value, int> = 0> bool read_single(T& ref) { if (!succ()) return false; bool neg = false; if (line[st] == '-') { neg = true; st++; } ref = T(0); while (isdigit(line[st])) { ref = 10 * ref + (line[st++] - '0'); } if (neg) ref = -ref; return true; } template <class T> bool read_single(vector<T>& ref) { for (auto& d : ref) { if (!read_single(d)) return false; } return true; } void read() {} template <class H, class... T> void read(H& h, T&... t) { bool f = read_single(h); assert(f); read(t...); } Scanner(FILE* _fp) : fp(_fp) {} }; struct Printer { public: template <bool F = false> void write() {} template <bool F = false, class H, class... T> void write(const H& h, const T&... t) { if (F) write_single(' '); write_single(h); write<true>(t...); } template <class... T> void writeln(const T&... t) { write(t...); write_single('\n'); } Printer(FILE* _fp) : fp(_fp) {} ~Printer() { flush(); } private: static constexpr size_t SIZE = 1 << 15; FILE* fp; char line[SIZE], small[50]; size_t pos = 0; void flush() { fwrite(line, 1, pos, fp); pos = 0; } void write_single(const char& val) { if (pos == SIZE) flush(); line[pos++] = val; } template <class T, enable_if_t<is_integral<T>::value, int> = 0> void write_single(T val) { if (pos > (1 << 15) - 50) flush(); if (val == 0) { write_single('0'); return; } if (val < 0) { write_single('-'); val = -val; // todo min } size_t len = 0; while (val) { small[len++] = char('0' + (val % 10)); val /= 10; } for (size_t i = 0; i < len; i++) { line[pos + i] = small[len - 1 - i]; } pos += len; } void write_single(const string& s) { for (char c : s) write_single(c); } void write_single(const char* s) { size_t len = strlen(s); for (size_t i = 0; i < len; i++) write_single(s[i]); } template <class T> void write_single(const vector<T>& val) { auto n = val.size(); for (size_t i = 0; i < n; i++) { if (i) write_single(' '); write_single(val[i]); } } }; Scanner sc(stdin); Printer pr(stdout); using ll=long long; //#define int ll #define rng(i,a,b) for(int i=int(a);i<int(b);i++) #define rep(i,b) rng(i,0,b) #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;} template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;} template<class t> using vc=vector<t>; template<class t> using vvc=vc<vc<t>>; using pi=pair<int,int>; using vi=vc<int>; template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p){ return os<<"{"<<p.a<<","<<p.b<<"}"; } template<class t> ostream& operator<<(ostream& os,const vc<t>& v){ os<<"{"; for(auto e:v)os<<e<<","; return os<<"}"; } #define mp make_pair #define mt make_tuple #define one(x) memset(x,-1,sizeof(x)) #define zero(x) memset(x,0,sizeof(x)) #ifdef LOCAL 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 dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__) #else #define dmp2(...) void(0) #endif using uint=unsigned; using ull=unsigned long long; template<class t,size_t n> ostream& operator<<(ostream&os,const array<t,n>&a){ return os<<vc<t>(all(a)); } template<int i,class T> void print_tuple(ostream&,const T&){ } template<int i,class T,class H,class ...Args> void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<<get<i>(t); print_tuple<i+1,T,Args...>(os,t); } template<class ...Args> ostream& operator<<(ostream&os,const tuple<Args...>&t){ os<<"{"; print_tuple<0,tuple<Args...>,Args...>(os,t); return os<<"}"; } template<class t> void print(t x,int suc=1){ cout<<x; if(suc==1) cout<<"\n"; if(suc==2) cout<<" "; } ll read(){ ll i; cin>>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } pi readpi(int off=0){ int a,b;cin>>a>>b; return pi(a+off,b+off); } template<class T> void print(const vector<T>&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } string readString(){ string s; cin>>s; return s; } template<class T> T sq(const T& t){ return t*t; } //#define CAPITAL void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)<<i)-1; } bool inc(int a,int b,int c){ return a<=b&&b<=c; } template<class t> void mkuni(vc<t>&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); #endif return uniform_int_distribution<ll>(l, r)(gen); } template<class t> void myshuffle(vc<t>&a){ rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template<class t> int lwb(const vc<t>&v,const t&a){ return lower_bound(all(v),a)-v.bg; } vvc<int> readGraph(int n,int m){ vvc<int> g(n); rep(i,m){ int a,b; cin>>a>>b; //sc.read(a,b); a--;b--; g[a].pb(b); g[b].pb(a); } return g; } vvc<int> readTree(int n){ return readGraph(n,n-1); } struct modinfo{uint mod,root;}; template<modinfo const&ref> struct modular{ static constexpr uint const &mod=ref.mod; static modular root(){return modular(ref.root);} uint v; //modular(initializer_list<uint>ls):v(*ls.bg){} modular(ll vv=0){s(vv%mod+mod);} modular& s(uint vv){ v=vv<mod?vv:vv-mod; return *this; } modular operator-()const{return modular()-*this;} modular& operator+=(const modular&rhs){return s(v+rhs.v);} modular&operator-=(const modular&rhs){return s(v+mod-rhs.v);} modular&operator*=(const modular&rhs){ v=ull(v)*rhs.v%mod; return *this; } modular&operator/=(const modular&rhs){return *this*=rhs.inv();} modular operator+(const modular&rhs)const{return modular(*this)+=rhs;} modular operator-(const modular&rhs)const{return modular(*this)-=rhs;} modular operator*(const modular&rhs)const{return modular(*this)*=rhs;} modular operator/(const modular&rhs)const{return modular(*this)/=rhs;} modular pow(int n)const{ modular res(1),x(*this); while(n){ if(n&1)res*=x; x*=x; n>>=1; } return res; } modular inv()const{return pow(mod-2);} /*modular inv()const{ int x,y; int g=extgcd<ll>(v,mod,x,y); assert(g==1); if(x<0)x+=mod; return modular(x); }*/ friend modular operator+(int x,const modular&y){ return modular(x)+y; } friend modular operator-(int x,const modular&y){ return modular(x)-y; } friend modular operator*(int x,const modular&y){ return modular(x)*y; } friend modular operator/(int x,const modular&y){ return modular(x)/y; } friend ostream& operator<<(ostream&os,const modular&m){ return os<<m.v; } friend istream& operator>>(istream&is,modular&m){ ll x;is>>x; m=modular(x); return is; } bool operator<(const modular&r)const{return v<r.v;} bool operator==(const modular&r)const{return v==r.v;} bool operator!=(const modular&r)const{return v!=r.v;} explicit operator bool()const{ return v; } }; //extern constexpr modinfo base{998244353,3}; extern constexpr modinfo base{1000000007,0}; //modinfo base{1,0}; using mint=modular<base>; const int vmax=(1<<21)+10; mint fact[vmax],finv[vmax],invs[vmax]; void initfact(){ fact[0]=1; rng(i,1,vmax){ fact[i]=fact[i-1]*i; } finv[vmax-1]=fact[vmax-1].inv(); for(int i=vmax-2;i>=0;i--){ finv[i]=finv[i+1]*(i+1); } for(int i=vmax-1;i>=1;i--){ invs[i]=finv[i]*fact[i-1]; } } mint choose(int n,int k){ return fact[n]*finv[n-k]*finv[k]; } mint binom(int a,int b){ return fact[a+b]*finv[a]*finv[b]; } mint catalan(int n){ return binom(n,n)-(n-1>=0?binom(n-1,n+1):0); } /* const int vmax=110; mint binbuf[vmax][vmax]; mint choose(int n,int k){ return binbuf[n-k][k]; } mint binom(int a,int b){ return binbuf[a][b]; } void initfact(){ binbuf[0][0]=1; rep(i,vmax)rep(j,vmax){ if(i)binbuf[i][j]+=binbuf[i-1][j]; if(j)binbuf[i][j]+=binbuf[i][j-1]; } } */ const int S=3; using Vec=array<mint,S>; struct Matrix{ array<mint,S> val[S]; Matrix(){} Matrix operator*(const Matrix&r)const{ Matrix res; rep(i,S)rep(j,S)rep(k,S) res[i][j]+=val[i][k]*r[k][j]; return res; } Matrix&operator*=(const Matrix&r){ return *this=*this*r; } array<mint,S>& operator[](int i){ return val[i]; } const array<mint,S>& operator[](int i)const{ return val[i]; } Vec operator*(const Vec&r)const{ Vec res; rep(i,S)rep(j,S)res[i]+=val[i][j]*r[j]; return res; } }; using V=Vec; using M=Matrix; V matpow_V(M a,int n,V res){ while(n){ if(n&1)res=a*res; a*=a; n>>=1; } return res; } signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); int n,m;sc.read(n,m); vi a(n+1); rng(i,2,n+1)sc.read(a[i]); vvc<int> g(n); rng(i,2,n)for(int j=i*2;j<n;j+=i)g[j].pb(i); vc<bool> ok(n); mint ans=0; auto add_pair=[&](int fr,int to){ M x; x[0][0]=a[fr]-1; x[1][0]=1; x[1][1]=a[to]-1; x[2][1]=1; x[2][2]=a[n]-1; V v; v[0]=1; v=matpow_V(x,m-1,v); ans+=v[2]; }; auto set_ok=[&](int i){ ok[i]=true; for(auto fr:g[i]) add_pair(fr,i); }; auto add_edge=[&](int fr,int to){ g[to].pb(fr); if(ok[to]){ add_pair(fr,to); } }; rng(i,2,n)if(n%i==0)set_ok(i); pr.writeln(ans.v); int q;sc.read(q); rep(_,q){ int x,y;sc.read(x,y); if(y==n){ set_ok(x); }else{ add_edge(x,y); } pr.writeln(ans.v); } }