結果
問題 | No.315 世界のなんとか3.5 |
ユーザー |
![]() |
提出日時 | 2019-12-29 05:31:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 178 ms / 2,000 ms |
コード長 | 2,345 bytes |
コンパイル時間 | 1,589 ms |
コンパイル使用メモリ | 113,536 KB |
実行使用メモリ | 22,912 KB |
最終ジャッジ日時 | 2024-10-13 09:03:25 |
合計ジャッジ時間 | 5,124 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#define popcount __builtin_popcountusing namespace std;typedef long long int ll;typedef pair<int, int> P;const ll MOD=1e9+7;ll solve(string a, int P){if(a.size()<=5){int x=0;for(int i=0; i<a.size(); i++){x*=10;x+=a[i]-'0';}ll ret=0;for(int i=1; i<=x; i++){if(i%P==0) continue;if(i%3==0) ret++;else{int j=i;while(j){if(j%10==3){ret++;break;}j/=10;}}}return ret;}int n=a.size();ll dp[2][2][3][200020]={};for(int k=1; k<a[0]-'0'; k++){if(k==3) dp[1][1][0][0]++;else dp[1][0][k%3][0]++;}if(a[0]-'0'==3) dp[0][1][0][0]++;else dp[0][0][(a[0]-'0')%3][0]++;for(int i=1; i<n-5; i++){for(int k=1; k<10; k++){if(k==3) dp[1][1][0][i]++;else dp[1][0][k%3][i]++;}}for(int i=1; i<n-5; i++){for(int j=0; j<3; j++){for(int k=0; k<10; k++){for(int l=0; l<2; l++){int p=l|(k==3);if(k<a[i]-'0'){(dp[1][p][(j+k)%3][i]+=dp[0][l][j][i-1])%=MOD;}else if(a[i]-'0'==k){(dp[0][p][(j+k)%3][i]+=dp[0][l][j][i-1])%=MOD;}(dp[1][p][(j+k)%3][i]+=dp[1][l][j][i-1])%=MOD;}}}}int x=0;for(int i=n-5; i<n; i++){x*=10; x+=a[i]-'0';}ll ret=0;for(int i=0; i<100000; i++){if(i%P==0) continue;bool myon=0;int i1=i;while(i1){if(i1%10==3){myon=1;break;}i1/=10;}if(i%3==0 || myon){ret++;ret%=MOD;}for(int j=0; j<3; j++){for(int l=0; l<2; l++){if((i+j)%3==0 || l || myon){(ret+=dp[1][l][j][n-6])%=MOD;if(i<=x) (ret+=dp[0][l][j][n-6])%=MOD;}}}}return ret;}int main(){string a, b;cin>>a>>b;int P; cin>>P;for(int i=(int)a.size()-1; i>=0; i--){if(a[i]!='0'){a[i]--;for(int j=i+1; j<a.size(); j++){a[j]='9';}break;}}if(a[0]=='0'){a=a.substr(1);}cout<<(solve(b, P)-solve(a, P)+MOD)%MOD<<endl;return 0;}