結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
![]() |
提出日時 | 2021-03-05 21:36:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 316 ms / 3,000 ms |
コード長 | 1,114 bytes |
コンパイル時間 | 4,090 ms |
コンパイル使用メモリ | 260,940 KB |
最終ジャッジ日時 | 2025-01-19 10:43:06 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint1000000007;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000001string s;mint get(int pos,int m,int f){static vector dp(10005,vector(100,vector<mint>(2,0)));static vector visited(10005,vector(100,vector<bool>(2,false)));if(visited[pos][m][f])return dp[pos][m][f];if(pos==s.size()){if(m==0)return 1;else return 0;}visited[pos][m][f] = true;mint ret = 0;int t = s[pos]-'0';for(int i=1;i<=9;i++){if(i<t){ret += get(pos+1,m*i%100,1);}else if(i==t){ret += get(pos+1,m*i%100,f);}else{if(f)ret += get(pos+1,m*i%100,f);}}dp[pos][m][f] = ret;return ret;}int main(){cin>>s;mint ans = 0;{vector<mint> dp(100,0);dp[1] = 1;rep(i,s.size()-1){vector<mint> ndp(100,0);rep(j,100){rep(k,10){if(k==0)continue;ndp[j*k%100] += dp[j];}}swap(dp,ndp);ans += dp[0];}}//cout<<ans.val()<<endl;ans += get(0,1,0);cout<<ans.val()<<endl;return 0;}