結果
問題 | No.1085 桁和の桁和 |
ユーザー |
![]() |
提出日時 | 2020-06-19 22:48:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 1,739 bytes |
コンパイル時間 | 1,964 ms |
コンパイル使用メモリ | 196,720 KB |
最終ジャッジ日時 | 2025-01-11 07:30:44 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define INF 1000000000 #define mod 1000000007 using ll=long long; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} ll pow_mod(ll x, ll n){ if(n==0) return 1; ll ret=pow_mod((x*x) % 9, n/2); if(n&1) ret=(ret*x)%9; return ret; } signed main(){ cin.tie(0); ios::sync_with_stdio(0); string s;cin>>s; int d;cin>>d; if(d==0){ bool f=true; for(auto c:s){ if(c!='0' and c!='?') f=false; } cout<<f<<endl; return 0; } bool f=true; for(auto c:s)if(c!='0' and c!='?') f=false; vector<ll> dp(10,0); dp[0]=1; reverse(ALL(s)); rep(i,(int)s.size()){ vector<ll> newdp(10,0); if(s[i]=='?'){ rep(t,10){ rep(j,10){ int to=(j+t)%9; newdp[to]+=dp[j]; newdp[to]%=mod; } } }else{ int t=s[i]-'0'; for(int j=0;j<10;j++){ int to=(j+t)%9; newdp[to]+=dp[j]; newdp[to]%=mod; } } swap(dp,newdp); } ll ans; if(f and d==9){ ans=dp[0]-1; if(ans<0) ans+=mod; }else{ ans=dp[d%9]; } cout<<ans<<endl; return 0; }