結果
問題 |
No.1085 桁和の桁和
|
ユーザー |
|
提出日時 | 2020-06-20 20:38:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 1,214 bytes |
コンパイル時間 | 225 ms |
コンパイル使用メモリ | 33,536 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-11-06 17:42:47 |
合計ジャッジ時間 | 1,819 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include<cstdio> #include<cstring> const long long mod = 1e9+7; char s[100001]; long long f[100001][10]; int digitSum(int u){ while(u>9){ int v = 0; while(u){ v += u%10; u /= 10; } u = v; } return u; } int main(){ //for(int i = 1; i <= 20; i++) printf("i = %d: %d\n",i,digitSum(i)); int d; scanf("%s%d",s+1,&d); int n = strlen(s+1); int sum = 0, cnt = 0; for(int i = 1; i <= n; i++){ if(s[i]!='?') sum += s[i]-'0'; else cnt++; } if(d==0){ if(sum==0) printf("1\n"); else printf("0\n"); } else{ int begin = (sum%9)-1; if(begin<0) begin += 9; f[0][begin] = 1; for(int i = 1; i <= cnt; i++){ for(int j = 0; j <= 8; j++){ f[i][j] = 0; for(int k = 0; k <= 9; k++){ int last = (j-k)%9; if(last<0) last += 9; f[i][j] = (f[i][j] + f[i-1][last])%mod; } } } if(d==9 && sum==0) f[cnt][d-1]--; if(f[cnt][d-1]<0) f[cnt][d-1] += mod; printf("%lld\n",f[cnt][d-1]); } return 0; }