結果
問題 | 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 longlong 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;}