結果
問題 | No.315 世界のなんとか3.5 |
ユーザー |
![]() |
提出日時 | 2017-01-01 22:21:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,033 ms / 2,000 ms |
コード長 | 2,034 bytes |
コンパイル時間 | 854 ms |
コンパイル使用メモリ | 95,916 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-16 05:23:01 |
合計ジャッジ時間 | 15,828 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <cassert> #include <iostream> #include <algorithm> #include <stack> #include <queue> #include <vector> #include <set> #include <map> #include <bitset> #include <functional> #include <numeric> using namespace std; #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define mp(a,b) make_pair((a),(b)) #define pb(a) push_back((a)) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<<((x))<<endl #define fi first #define se second #define INF 2147483600 #define MOD 1000000007 #define long long long long dp[2][2][2][3][800]; // [-][EQ?][3を使った][mod3][mod p] // 数値,8の倍数を加算するか,8の倍数でないものを加算するか,sとイコールを含めるか long solve(string &s, int p, bool eq=true){ int n = s.size(); auto prev = dp[0]; auto crnt = dp[1]; fill(prev[0][0][0], prev[2][0][0], 0); prev[1][0][0][0] = 1; rep(i,max(n-5,0)){ fill(crnt[0][0][0], crnt[2][0][0], 0); rep(j,2) rep(k,3){ rep(m,10) (crnt[0][j|(m==3)][(k*10+m)%3][0] += prev[0][j][k][0]) %= MOD; int mx = s[i]-'0'; rep(m,mx+1) (crnt[m==mx][j|(m==3)][(k*10+m)%3][0] += prev[1][j][k][0]) %= MOD; } swap(prev, crnt); } repl(i,max(n-5,0),n){ fill(crnt[0][0][0], crnt[2][0][0], 0); rep(j,2) rep(k,3) rep(l,p){ rep(m,10) (crnt[0][j|(m==3)][(k*10+m)%3][(l*10+m)%p] += prev[0][j][k][l]) %= MOD; int mx = s[i]-'0'; rep(m,mx+1) (crnt[m==mx][j|(m==3)][(k*10+m)%3][(l*10+m)%p] += prev[1][j][k][l]) %= MOD; } swap(prev, crnt); } long ret = 0; rep(i,2) if(i==0 || eq){ rep(j,3)repl(k,1,p) ret = (ret+prev[i][1][j][k])%MOD; // 3を使った repl(k,1,p) ret = (ret+prev[i][0][0][k])%MOD; // 3を使わずmod3=0 } return ret; } int main(){ std::cin.tie(0); std::ios::sync_with_stdio(false); string a,b; int p; cin>>a>>b>>p; cout << (solve(b,p,true) - solve(a,p,false) + MOD)%MOD << endl; return 0; }