結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
![]() |
提出日時 | 2021-03-29 03:11:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 38 ms / 3,000 ms |
コード長 | 2,968 bytes |
コンパイル時間 | 980 ms |
コンパイル使用メモリ | 86,816 KB |
実行使用メモリ | 16,224 KB |
最終ジャッジ日時 | 2024-11-29 09:39:59 |
合計ジャッジ時間 | 2,409 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; using ll = long long int; constexpr ll MOD = 1'000'000'007; int main(){ string n0; cin >> n0; vector<int> n(n0.length()+1); n[0] = 0; for(int i = 0; i < n0.length(); i++) n[i+1] = n0[i]-'0'; vector<vector<vector<vector<vector<ll>>>>> dp(n.size(), vector<vector<vector<vector<ll>>>>(2, vector<vector<vector<ll>>>(3, vector<vector<ll>>(3, vector<ll>(2, 0))))); dp[0][0][0][0][0] = 1; //cerr << "dp start" << endl; //for(int i = 0; i < n.size(); i++) cerr << n[i] << " "; for(int i = 1; i < n.size(); i++){ // from smaller == 1 for(int smaller = 0; smaller < 2; smaller++){ for(int cnt2 = 0; cnt2 < 3; cnt2++){ for(int cnt5 = 0; cnt5 < 3; cnt5++){ //cerr << n[i] << endl; for(int nonzero = 0; nonzero < 2; nonzero++){ for(int j = 0; j <= ((smaller == 1) ? 9 : n[i]); j++){ //cerr << i << " " << smaller << " " << cnt2 << " " << cnt5 << " " << j << endl; if(j == 5){ dp[i][(smaller == 1 || j < n[i]) ? 1 : 0][cnt2][min(cnt5+1, 2)][1] += dp[i-1][smaller][cnt2][cnt5][nonzero]; dp[i][(smaller == 1 || j < n[i]) ? 1 : 0][cnt2][min(cnt5+1, 2)][1] %= MOD; }else if(j == 2 || j == 6){ dp[i][(smaller == 1 || j < n[i]) ? 1 : 0][min(cnt2+1, 2)][cnt5][1] += dp[i-1][smaller][cnt2][cnt5][nonzero]; dp[i][(smaller == 1 || j < n[i]) ? 1 : 0][min(cnt2+1, 2)][cnt5][1] %= MOD; }else if(j == 4 || j == 8){ dp[i][(smaller == 1 || j < n[i]) ? 1 : 0][2][cnt5][1] += dp[i-1][smaller][cnt2][cnt5][nonzero]; dp[i][(smaller == 1 || j < n[i]) ? 1 : 0][2][cnt5][1] %= MOD; }else if(j == 0){ dp[i][(smaller == 1 || j < n[i]) ? 1 : 0][cnt2][cnt5][0] += (nonzero == 0) ? dp[i-1][smaller][cnt2][cnt5][nonzero] : 0; dp[i][(smaller == 1 || j < n[i]) ? 1 : 0][cnt2][cnt5][0] %= MOD; }else{ dp[i][(smaller == 1 || j < n[i]) ? 1 : 0][cnt2][cnt5][1] += dp[i-1][smaller][cnt2][cnt5][nonzero]; dp[i][(smaller == 1 || j < n[i]) ? 1 : 0][cnt2][cnt5][1] %= MOD; } } } } } } } ll ans = dp[n0.size()][0][2][2][1] + dp[n0.size()][1][2][2][1]; cout << ans % MOD << endl; return 0; }