結果
問題 | No.260 世界のなんとか3 |
ユーザー |
![]() |
提出日時 | 2019-03-28 19:50:16 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,754 bytes |
コンパイル時間 | 1,314 ms |
コンパイル使用メモリ | 141,232 KB |
実行使用メモリ | 32,640 KB |
最終ジャッジ日時 | 2024-11-30 13:48:01 |
合計ジャッジ時間 | 5,226 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 2 WA * 23 RE * 2 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <utility> #include <numeric> #include <array> #include <cmath> #include <memory> using namespace std; //変数デバッグ #define DEB(variable) cout << #variable << '=' << variable << endl //for簡易表記(引数ミス防止) #define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++) #define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--) #define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++) constexpr long long int linf = numeric_limits<long long int>::max()-5; constexpr int inf= numeric_limits<int>::max()-5; constexpr long long int mod = 1000000007; int main(){ string s, t; cin >> s >> t; const int sn = (int)s.size(), tn = (int)t.size(); int tmp = sn - 1; while(s[tmp]=='0'){ s[tmp] = '9'; tmp--; } s[tmp]--; vector<vector<vector<vector<vector<long long int>>>>> dp1(10001,vector<vector<vector<vector<long long int>>>>(2,vector<vector<vector<long long int>>>(2,vector<vector<long long int>>(3,vector<long long int>(8,0))))),dp2(10001,vector<vector<vector<vector<long long int>>>>(2,vector<vector<vector<long long int>>>(2,vector<vector<long long int>>(3,vector<long long int>(8,0))))); dp1[0][0][0][0][0] = 1; dp2[0][0][0][0][0] = 1; int x; REP(i,tn){ REP(j,2){ REP(k,2){ REP(l,3){ REP(m,8){ x = j ? 9 : (int)(t[i] - '0'); REP(n,x+1){ dp1[i + 1][j || n < x][k || n == 3][(l + n) % 3][(m * 10 + n) % 8] += dp1[i][j][k][l][m]; } } } } } } REP(i,sn){ REP(j,2){ REP(k,2){ REP(l,3){ REP(m,8){ x = j ? 9 : (int)(s[i] - '0'); REP(n,x+1){ dp2[i + 1][j || n < x][k || n == 3][(l + n) % 3][(m * 10 + n) % 8] += dp2[i][j][k][l][m]; } } } } } } long long int result = 0; REP(i,2){ REP(j,2){ REP(k,3){ REP(l,8){ if((j||k==0)&&l!=0){ result += dp1[tn][i][j][k][l]-dp2[sn][i][j][k][l]; result %= mod; } } } } } cout << result << endl; return 0; }