結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
![]() |
提出日時 | 2021-03-05 22:00:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 3,000 ms |
コード長 | 1,109 bytes |
コンパイル時間 | 1,709 ms |
コンパイル使用メモリ | 167,512 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-07 01:51:41 |
合計ジャッジ時間 | 2,669 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long int ll;typedef pair<ll,ll> P;typedef vector<ll> VI;typedef vector<VI> VVI;#define REP(i,n) for(int i=0;i<(n);i++)#define ALL(v) v.begin(),v.end()constexpr ll MOD=1000000007;constexpr ll INF=2e18;int main(){string s; cin >> s;int n=s.size();ll dp[10010][2][3][3]={0};REP(i,n-1)dp[i+1][1][0][0]=1;dp[0][0][0][0]=1;REP(i,n){REP(j,3)REP(k,3)REP(l,10){if(l==0) continue;int toj=j, tok=k;if(l==2||l==6)toj=min(2,j+1);else if(l==4||l==8)toj=min(2,j+2);else if(l==5)tok=min(2,k+1);dp[i+1][1][toj][tok]+=dp[i][1][j][k];if(l<s[i]-'0')dp[i+1][1][toj][tok]+=dp[i][0][j][k];else if(l==s[i]-'0')dp[i+1][0][toj][tok]+=dp[i][0][j][k];dp[i+1][0][toj][tok]%=MOD;dp[i+1][1][toj][tok]%=MOD;}}ll ans=dp[n][1][2][2]+dp[n][0][2][2];cout << ans%MOD << endl;return 0;}