結果
問題 | No.315 世界のなんとか3.5 |
ユーザー |
![]() |
提出日時 | 2015-12-01 05:51:17 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 165 ms / 2,000 ms |
コード長 | 1,417 bytes |
コンパイル時間 | 555 ms |
コンパイル使用メモリ | 64,252 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-23 14:35:35 |
合計ジャッジ時間 | 4,450 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <vector>#include <iostream>#include <string>using namespace std;constexpr long long MOD = 1000000007;long long calc(string& s, int p){vector<vector<long long>> dp(800, vector<long long>(16, 0));vector<vector<long long>> dp_(800, vector<long long>(16, 0));dp[0][0] = 1;int sz = s.size();for(int i=0; i<sz; i++){int k = s[i] - '0';for(int j=0; j<((i<sz-5)?1:p); j++){for(int a=0; a<2; a++)for(int b=0; b<3; b++)for(int c=0; c<2; c++){int s=(a<<3)|(b<<1)|c;long long val = dp[j][s];dp[j][s] = 0;for(int d=0; d<10; d++){if(a==0 && d>k) continue;int a_ = a | (d<k);int b_ = (b+d)%3;int c_ = c | (d==3);int s_ = (a_<<3)|(b_<<1)|c_;int j_ = (i<sz-5)?0:(j*10+d)%p;dp_[j_][s_] += val;if(dp_[j_][s_]>=MOD) dp_[j_][s_]-=MOD;}}}swap(dp,dp_);}long long ret = 0;for(int j=1; j<p; j++)for(int a=0; a<2; a++)for(int b=0; b<3; b++)for(int c=0; c<2; c++){if(b!=0 && c==0) continue;int s=(a<<3)|(b<<1)|c;ret += dp[j][s];if(ret>=MOD) ret-=MOD;}return ret;}int main(){string a,b;int p;cin >> a >> b >> p;long long ans = calc(b, p);ans = (ans - calc(a,p) + MOD) % MOD;int x=0;int y=0;int z=0;for(auto c:a){int k = c-'0';x = (x+k)%3;y |= k==3;z = (z*10+k)%p;}if((x==0 || y==1) && z!=0){ans++;ans %= MOD;}cout << ans << endl;return 0;}