結果
問題 | No.1085 桁和の桁和 |
ユーザー |
![]() |
提出日時 | 2020-06-19 22:17:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 3,454 bytes |
コンパイル時間 | 1,768 ms |
コンパイル使用メモリ | 167,088 KB |
実行使用メモリ | 11,520 KB |
最終ジャッジ日時 | 2024-11-06 17:36:07 |
合計ジャッジ時間 | 3,084 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define lli long long int#define REP(i,s,n) for(lli i=s;i<n;i++)#define NUM 2520#define INF (1LL<<50)#define DEBUG 0#define mp(a,b) make_pair(a,b)#define SORT(V) sort(V.begin(),V.end())#define PI (3.141592653589794)#define TO_STRING(VariableName) # VariableName#define LOG(x) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<endl;#define LOG2(x,y) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<endl;#define LOG3(x,y,z) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;#define LOG4(w,x,y,z) if(DEBUG)cout<<TO_STRING(w)<<"="<<w<<" "<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }// modint: mod 計算を int を扱うように扱える構造体template<int MOD> struct Fp {long long val;constexpr Fp(long long v = 0) noexcept : val(v % MOD) {if (val < 0) val += MOD;}constexpr int getmod() { return MOD; }constexpr Fp operator - () const noexcept {return val ? MOD - val : 0;}constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }constexpr Fp& operator += (const Fp& r) noexcept {val += r.val;if (val >= MOD) val -= MOD;return *this;}constexpr Fp& operator -= (const Fp& r) noexcept {val -= r.val;if (val < 0) val += MOD;return *this;}constexpr Fp& operator *= (const Fp& r) noexcept {val = val * r.val % MOD;return *this;}constexpr Fp& operator /= (const Fp& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}constexpr bool operator == (const Fp& r) const noexcept {return this->val == r.val;}constexpr bool operator != (const Fp& r) const noexcept {return this->val != r.val;}friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {return os << x.val;}friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {if (n == 0) return 1;auto t = modpow(a, n / 2);t = t * t;if (n & 1) t = t * a;return t;}};const int MOD = 1000000007;using mint = Fp<MOD>;mint dp[100100][10];void solve(){string s;lli d;cin>>s>>d;lli sum = 0;lli cnt = 0;dp[0][0]=1;REP(i,0,s.size()){if(s[i]=='?'){REP(j,0,10){REP(k,0,10){lli nex = (j+k);if(nex>=10){nex -= 9;}dp[i+1][nex] += dp[i][j];}}}else{REP(j,0,10){lli nex = j + (s[i]-'0');if(nex>=10){nex-=9;}dp[i+1][nex] += dp[i][j];}}}cout<<dp[s.size()][d]<<endl;}int main(){lli t;t=1;while(t--)solve();return 0;}