結果
問題 | No.315 世界のなんとか3.5 |
ユーザー |
![]() |
提出日時 | 2017-09-11 23:26:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 426 ms / 2,000 ms |
コード長 | 5,079 bytes |
コンパイル時間 | 991 ms |
コンパイル使用メモリ | 98,128 KB |
実行使用メモリ | 23,680 KB |
最終ジャッジ日時 | 2024-11-07 15:52:26 |
合計ジャッジ時間 | 7,558 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include<iostream>#include<algorithm>#include<functional>#include<string>#include<vector>#include<map>#include<set>#include<tuple>#include<stack>#include<queue>#include<deque>#include<sstream>#include<stdio.h>#include<math.h>#include<stdlib.h>#include<bitset>#include<time.h>#include<cstdlib>#include<cassert>#define ll long long#define fi first#define se secondusing namespace std;const ll MOD=(ll)1e9+7;string a,b,p;ll dp[200010][2][2][3];ll dp1[10][2][2][3][800];//ll dp[200010][2][2][3][8][2][2];inline ll solve(string s,string p){int n=(int)s.length();int m=(int)p.length();int h=stoi(p);m+=2;if(n-m<=0)return -114;for(int i=0;i<200010;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)for(int l=0;l<3;l++)dp[i][j][k][l]=0;dp[0][0][0][0]=1;for(int i=0;i<n-m;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)for(int l=0;l<3;l++){int lim=j?9:s[i]-'0';for(int d=0;d<lim+1;d++){(dp[i+1][j || d<lim][k || d==3][(10*l+d)%3]+=dp[i][j][k][l])%=MOD;}}for(int i=0;i<10;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)for(int l=0;l<3;l++)for(int o=0;o<800;o++)dp1[i][j][k][l][o]=0;for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<3;k++){dp1[0][i][j][k][0]=dp[n-m][i][j][k];}for(int i=0;i<m;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)for(int l=0;l<3;l++)for(int o=0;o<h;o++){int lim=j?9:s[n-m+i]-'0';for(int d=0;d<lim+1;d++){(dp1[i+1][j || d<lim][k || d==3][(10*l+d)%3][(10*o+d)%h]+=dp1[i][j][k][l][o])%=MOD;}}ll res=0;for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<3;k++)for(int l=0;l<h;l++){if((j || k==0) && (l!=0))(res+=dp1[m][i][j][k][l])%=MOD;}return res;}inline ll solve2(string s,int p){int n=(int)s.length();for(int i=0;i<10;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)for(int l=0;l<3;l++)for(int o=0;o<800;o++)dp1[i][j][k][l][o]=0;dp1[0][0][0][0][0]=1;for(int i=0;i<n;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)for(int l=0;l<3;l++)for(int m=0;m<p;m++){int lim=j?9:s[i]-'0';for(int d=0;d<lim+1;d++){(dp1[i+1][j || d<lim][k || d==3][(10*l+d)%3][(10*m+d)%p]+=dp1[i][j][k][l][m])%=MOD;}}ll res=0;for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<3;k++)for(int l=0;l<p;l++){if((j || k==0) && l!=0)(res+=dp1[n][i][j][k][l])%=MOD;}return res;}/*inline ll solve(string s,int p){int n=s.length();dp[0][0][0][0][0][0][0]=1;for(int i=0;i<n;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)for(int l=0;l<3;l++)for(int m=0;m<8;m++)for(int o=0;o<2;o++)for(int h=0;h<2;h++){int lim=j?9:s[i]-'0';for(int d=0;d<lim+1;d++){if(i==n-2){(dp[i+1][j || d<lim][k || d==3][(10*l+d)%3][(10*m+d)%8][o || d==0][h]+=dp[i][j][k][l][m][o][h])%=MOD;}else if(i==n-1){(dp[i+1][j || d<lim][k || d==3][(10*l+d)%3][(10*m+d)%8][o][h || d==0]+=dp[i][j][k][l][m][o][h])%=MOD;}else{(dp[i+1][j || d<lim][k || d==3][(10*l+d)%3][(10*m+d)%8][o][h]+=dp[i][j][k][l][m][o][h])%=MOD;}}}ll res=0;if(p==8){for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<3;k++)for(int l=0;l<8;l++)for(int m=0;m<2;m++)for(int o=0;o<2;o++){if((j || k==0) && l!=0)(res+=dp[n][i][j][k][l][m][o])%=MOD;}}else if(p==80){for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<3;k++)for(int l=0;l<8;l++)for(int m=0;m<2;m++)for(int o=0;o<2;o++){if((j || k==0) && (l!=0 || o==1))(res+=dp[n-1][i][j][k][l][m][o])%=MOD;if((j || k==0) && (l!=}}else{for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<3;k++)for(int l=0;l<8;l++)for(int m=0;m<2;m++)for(int o=0;o<2;o++){if((j || k==0) && (l!=0 || m!=1 || o!=1))(res+=dp[n][i][j][k][l][m][o])%=MOD;}}return res;}*/inline string min1(string s){for(int i=(int)s.length()-1;i>=0;i--){int now=s[i]-'0';if(now-1<0){s[i]='9';}else{s[i]=char('0'+now-1);break;}}for(int i=0;i<(int)s.length();i++){if(s=="0")break;if(s[i]=='0')s=s.substr(1,s.length()-1);else break;}return s;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout<<fixed;#ifdef LOCAL_DEFINEfreopen("in", "r", stdin);freopen("out","w",stdout);#endifcin>>a>>b>>p;string newa=min1(a);ll ansb=solve(b,p);if(ansb==-114)ansb=solve2(b,stoi(p));ll ansa=solve(newa,p);if(ansa==-114)ansa=solve2(newa,stoi(p));//cout<<ansa<<" "<<ansb<<endl;cout<<(ansb+MOD-ansa)%MOD<<"\n";#ifdef LOCAL_DEFINEcerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";#endifreturn 0;}