結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
👑 ![]() |
提出日時 | 2021-03-05 22:43:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 49 ms / 3,000 ms |
コード長 | 842 bytes |
コンパイル時間 | 4,178 ms |
コンパイル使用メモリ | 250,828 KB |
最終ジャッジ日時 | 2025-01-19 11:38:46 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using ll=long long;using ull=unsigned long long;#define rep(i,n) for(int i=0; i<(n); i++)using mll=atcoder::static_modint<1000000007>;string N;mll dp1[10002][100];mll dp[10002][100];mll dpf[10002][100];int main(){cin>>N;int n=N.size();rep(i,n+1) rep(j,100) dp1[i][j]=dp[i][j]=dpf[i][j]=0;mll ans=0;dp1[0][1]=1;rep(i,n-1){for(int x=1; x<=9; x++) rep(t,100) dp1[i+1][t*x%100]+=dp1[i][t];ans+=dp1[i+1][0];}dpf[0][1]=1;rep(i,n){int d=N[n-1-i]-'0';if(d!=0) rep(t,100) dp[i+1][t*d%100]+=dp[i][t];for(int x=1; x<d; x++) rep(t,100) dp[i+1][t*x%100]+=dp1[i][t];}ans+=dp[n][0];int t=1; for(char c:N){ if(c=='0'){ t=1; break; } t=t*(c-'0')%100; }if(t==0) ans++;printf("%u\n",ans.val());return 0;}