結果
問題 | No.315 世界のなんとか3.5 |
ユーザー | beet |
提出日時 | 2018-12-03 20:37:03 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,438 ms / 2,000 ms |
コード長 | 5,838 bytes |
コンパイル時間 | 2,095 ms |
コンパイル使用メモリ | 203,888 KB |
実行使用メモリ | 190,780 KB |
最終ジャッジ日時 | 2023-09-17 21:17:55 |
合計ジャッジ時間 | 25,934 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
165,212 KB |
testcase_01 | AC | 43 ms
165,136 KB |
testcase_02 | AC | 43 ms
165,216 KB |
testcase_03 | AC | 42 ms
165,112 KB |
testcase_04 | AC | 42 ms
165,424 KB |
testcase_05 | AC | 43 ms
165,192 KB |
testcase_06 | AC | 42 ms
165,108 KB |
testcase_07 | AC | 42 ms
165,208 KB |
testcase_08 | AC | 42 ms
165,176 KB |
testcase_09 | AC | 42 ms
165,268 KB |
testcase_10 | AC | 42 ms
165,152 KB |
testcase_11 | AC | 43 ms
165,300 KB |
testcase_12 | AC | 658 ms
177,924 KB |
testcase_13 | AC | 659 ms
177,968 KB |
testcase_14 | AC | 737 ms
177,780 KB |
testcase_15 | AC | 740 ms
177,892 KB |
testcase_16 | AC | 739 ms
177,796 KB |
testcase_17 | AC | 741 ms
177,796 KB |
testcase_18 | AC | 655 ms
177,968 KB |
testcase_19 | AC | 661 ms
177,988 KB |
testcase_20 | AC | 657 ms
177,908 KB |
testcase_21 | AC | 658 ms
178,080 KB |
testcase_22 | AC | 741 ms
177,968 KB |
testcase_23 | AC | 743 ms
177,888 KB |
testcase_24 | AC | 742 ms
178,116 KB |
testcase_25 | AC | 743 ms
177,796 KB |
testcase_26 | AC | 743 ms
177,968 KB |
testcase_27 | AC | 744 ms
177,800 KB |
testcase_28 | AC | 697 ms
177,956 KB |
testcase_29 | AC | 1,375 ms
190,716 KB |
testcase_30 | AC | 1,376 ms
190,680 KB |
testcase_31 | AC | 1,383 ms
190,704 KB |
testcase_32 | AC | 1,438 ms
190,780 KB |
testcase_33 | AC | 1,272 ms
190,536 KB |
testcase_34 | AC | 1,329 ms
190,756 KB |
testcase_35 | AC | 1,386 ms
190,772 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; 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,T MOD = 1000000007> struct Mint{ 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; } 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-(){return v?MOD-v: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;} // find x s.t. a^x = b static T log(Mint a,Mint b){ const T sq=40000; unordered_map<T, T> dp; dp.reserve(sq); Mint res(1); for(int r=0;r<sq;r++){ if(!dp.count(res)) dp[res]=r; res*=a; } Mint p=pow(a.inv(),sq); res=b; for(int q=0;q<=MOD/sq+1;q++){ if(dp.count(res)){ T idx=q*sq+dp[res]; if(idx>0) return idx; } res*=p; } return T(-1); } static vector<Mint> fact,finv,invs; static void init(int n){ if(n+1<=(signed)fact.size()) return; fact.assign(n+1,1); finv.assign(n+1,1); invs.assign(n+1,1); for(int i=1;i<=n;i++) fact[i]=fact[i-1]*Mint(i); finv[n]=Mint(1)/fact[n]; for(int i=n;i>=1;i--) finv[i-1]=finv[i]*Mint(i); for(int i=1;i<=n;i++) invs[i]=finv[i]*fact[i-1]; } static Mint comb(long long n,int k){ Mint res(1); for(int i=0;i<k;i++){ res*=Mint(n-i); res/=Mint(i+1); } return res; } static Mint C(int n,int k){ if(n<k||k<0) return Mint(0); init(n); return fact[n]*finv[n-k]*finv[k]; } static Mint P(int n,int k){ if(n<k||k<0) return Mint(0); init(n); return fact[n]*finv[n-k]; } static Mint H(int n,int k){ if(n<0||k<0) return Mint(0); if(!n&&!k) return Mint(1); init(n+k-1); return C(n+k-1,k); } static Mint S(int n,int k){ Mint res; init(k); for(int i=1;i<=k;i++){ Mint tmp=C(k,i)*Mint(i).pow(n); if((k-i)&1) res-=tmp; else res+=tmp; } return res*=finv[k]; } static vector<vector<Mint> > D(int n,int m){ vector<vector<Mint> > dp(n+1,vector<Mint>(m+1,0)); dp[0][0]=Mint(1); for(int i=0;i<=n;i++){ for(int j=1;j<=m;j++){ if(i-j>=0) dp[i][j]=dp[i][j-1]+dp[i-j][j]; else dp[i][j]=dp[i][j-1]; } } return dp; } static Mint B(int n,int k){ Mint res; for(int j=1;j<=k;j++) res+=S(n,j); return res; } static Mint montmort(int n){ Mint res; init(n); for(int k=2;k<=n;k++){ if(k&1) res-=finv[k]; else res+=finv[k]; } return res*=fact[n]; } static Mint LagrangePolynomial(vector<Mint> &y,Mint t){ int n=y.size()-1; if(t.v<=n) return y[t.v]; init(n+1); Mint num(1); for(int i=0;i<=n;i++) num*=t-Mint(i); Mint res; for(int i=0;i<=n;i++){ Mint tmp=y[i]*num/(t-Mint(i))*finv[i]*finv[n-i]; if((n-i)&1) res-=tmp; else res+=tmp; } return res; } }; template<typename T,T MOD> vector<Mint<T, MOD> > Mint<T, MOD>::fact = vector<Mint<T, MOD> >(); template<typename T,T MOD> vector<Mint<T, MOD> > Mint<T, MOD>::finv = vector<Mint<T, MOD> >(); template<typename T,T MOD> vector<Mint<T, MOD> > Mint<T, MOD>::invs = vector<Mint<T, MOD> >(); //INSERT ABOVE HERE using M = Mint<int>; const int MAX = 2e5+100; // aho M dp1[2][2][3][MAX]; bool used1[2][2][3][MAX]; M dfs1(string &s,int t,int f,int x,int i){ M &res=dp1[t][f][x][i]; if(used1[t][f][x][i]) return res; res=0; used1[t][f][x][i]=1; if(i==(int)s.size()) return res=M(f||!x); for(int k=0;k<=(t?s[i]-'0':9);k++) res+=dfs1(s,t&&(k==s[i]-'0'),f||(k==3),(x*10+k)%3,i+1); return res; } M solve1(string a,string b){ M res; memset(used1,0,sizeof(used1)); res+=dfs1(b,1,0,0,0); memset(used1,0,sizeof(used1)); res-=dfs1(a,1,0,0,0); int thr=count(a.begin(),a.end(),'3'); int tmp=0; for(int i=0;i<(int)a.size();i++) tmp=(tmp*10+a[i]-'0')%3; if(thr||!tmp) res+=M(1); return res; } // aho & haji M dp2[2][2][3][8][MAX]; int used2[2][2][3][8][MAX]; M dfs2(string &s,int t,int f,int x,int y,int i,int u){ M &res=dp2[t][f][x][y][i]; if(i==(int)s.size()) return res=M((f||!x)&&!y); int flg=(used2[t][f][x][y][i]&&!t); if(flg||used2[t][f][x][y][i]==u) return res; res=0; used2[t][f][x][y][i]=u; for(int k=0;k<=(t?s[i]-'0':9);k++) res+=dfs2(s,t&&(k==s[i]-'0'),f||(k==3),(x*10+k)%3,(y*10+k)%8,i+1,u); return res; } M solve2(string a,string b,int p){ M res; int thr=count(a.begin(),a.end(),'3'); int tmp=0,ppp=0; for(int i=0;i<(int)a.size();i++){ tmp=(tmp*10+a[i]-'0')%3; ppp=(ppp*10+a[i]-'0')%p; } if((thr||!tmp)&&!ppp) res+=M(1); while(p%10==0){ if(!a.empty()) a.pop_back(); if(!b.empty()) b.pop_back(); p/=10; } assert(p==8); if(a.size()<b.size()) a=string(b.size()-a.size(),'0')+a; memset(used2,0,sizeof(used2)); res+=dfs2(b,1,0,0,0,0,1); res-=dfs2(a,1,0,0,0,0,2); return res; } signed main(){ string a,b; int p; cin>>a>>b>>p; M ans; ans+=solve1(a,b); ans-=solve2(a,b,p); cout<<ans.v<<endl; return 0; }