結果
問題 | No.1407 Kindness |
ユーザー |
|
提出日時 | 2021-04-04 08:05:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 23 ms / 2,000 ms |
コード長 | 5,562 bytes |
コンパイル時間 | 1,261 ms |
コンパイル使用メモリ | 112,144 KB |
実行使用メモリ | 15,872 KB |
最終ジャッジ日時 | 2024-12-26 10:33:56 |
合計ジャッジ時間 | 3,132 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include<algorithm>#include<bitset>#include<cmath>#include<complex>#include<deque>#include<functional>#include<iomanip>#include<iostream>#include<iterator>#include<map>#include<numeric>#include<queue>#include<set>#include<stack>#include<string>#include<unordered_map>#include<unordered_set>#include<utility>#include<vector>#include<chrono>using namespace std;#define rep(i,n) for(int i=0; i<(n); i++)#define FOR(i,x,n) for(int i=x; i<(n); i++)#define vint(a,n) vint a(n); rep(i, n) cin >> a[i];#define vll(a,n) vll a(n); rep(i, n) cin >> a[i];#define ALL(n) begin(n),end(n)#define RALL(n) rbegin(n),rend(n)#define MOD (1000000007)// #define MOD (998244353)#define INF (1e9+7)#define INFL (2e18)typedef long long ll;typedef unsigned int ui;typedef unsigned long long ull;using vint=vector<int>;using vll=vector<ll>;using vbool=vector<bool>;using P=pair<ll,ll>;template<class T>using arr=vector<vector<T>>;template<class T>int popcount(T &a){int c=0; rep(i, 8*(int)sizeof(a)){if((a>>i)&1) c++;} return c;}template<class T>void pl(T x){cout << x << " ";}template<class T>void pr(T x){cout << x << endl;}template <class T, class... Ts> inline void pr(T Tar, Ts... ts) { std::cout << Tar << " "; pr(ts...); return; }template<class T>void prvec(vector<T>& a){if(a.size()>0){rep(i, (int)a.size()-1){pl(a[i]);} pr(a.back());}else{pr("");}}template<class T>void prarr(arr<T>& a){rep(i, (int)a.size()) if(a[i].empty()) pr(""); else prvec(a[i]);}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; }template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){fill( (T*)array, (T*)(array+N), val );}// modint: mod 計算を int を扱うように扱える構造体template<ll mod> class modint{public:ll val=0;//コンストラクタmodint(ll x=0){while(x<0)x+=mod;val=x%mod;}//コピーコンストラクタmodint(const modint &r){val=r.val;}//算術演算子modint operator -(){return modint(-val);} //単項modint operator +(const modint &r){return modint(*this)+=r;}modint operator -(const modint &r){return modint(*this)-=r;}modint operator *(const modint &r){return modint(*this)*=r;}modint operator /(const modint &r){return modint(*this)/=r;}//代入演算子modint &operator +=(const modint &r){val+=r.val;if(val>=mod)val-=mod;return *this;}modint &operator -=(const modint &r){if(val<r.val)val+=mod;val-=r.val;return *this;}modint &operator *=(const modint &r){val=val*r.val%mod;return *this;}modint &operator /=(const modint &r){ll a=r.val,b=mod,u=1,v=0;while(b){ll 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;}modint& operator++() {++val; return *this;}modint& operator--() {--val; return *this;}modint operator++(int) {val++; return *this;}modint operator--(int) {val--; return *this;}//等価比較演算子bool operator ==(const modint& r){return this->val==r.val;}bool operator <(const modint& r){return this->val<r.val;}bool operator <=(const modint& r){return this->val<=r.val;}bool operator >(const modint& r){return this->val>r.val;}bool operator >=(const modint& r){return this->val>=r.val;}bool operator !=(const modint& r){return this->val!=r.val;}};using mint = modint<MOD>;//入出力ストリームistream &operator >>(istream &is,mint& x){//xにconst付けないll t;is >> t;x=t;return (is);}ostream &operator <<(ostream &os,const mint& x){return os<<x.val;}//累乗mint modpow(mint a,ll n){if(n==0)return 1;mint t=modpow(a,n/2);t=t*t;if(n&1)t=t*a;return t;}// 行列累乗template<class T>arr<T> modpowmat(arr<T> &a, ll n){int s = a.size();arr<T> b(s, vector<T>(s, 0));rep(i, s) b[i][i] = 1;while(n>0){if(n&1) {arr<T> c(s, vector<T>(s, 0));rep(i, s) rep(j, s) rep(k, s) c[i][j] += a[i][k] * b[k][j];b = c;}arr<T> c(s, vector<T>(s, 0));rep(i, s) rep(j, s) rep(k, s) c[i][j] += a[i][k] * a[k][j];a = c;n >>= 1;}return b;}//二項係数の計算#define MAXR 300000mint fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];//テーブルの作成void COMinit() {fac[0]=fac[1]=1;finv[0]=finv[1]=1;inv[1]=1;FOR(i,2,MAXR){fac[i]=fac[i-1]*mint(i);inv[i]=-inv[MOD%i]*mint(MOD/i);finv[i]=finv[i-1]*inv[i];}}//演算部分mint PER(ll n, ll k){if(n<k)return 0;if(n<0 || k<0)return 0;return fac[n]*finv[n-k];}mint COM(ll n,ll k){return PER(n, k)*finv[k];}int main(){string s; cin >> s;int n = s.size();arr<mint> dp(n+1, vector<mint>(2, 0));rep(i, n) FOR(j, 1, 10){int p = s[i] - '0';if(p > j){dp[i+1][0] += (dp[i][0] + dp[i][1])*j;dp[i+1][0] += j;}else if(p==j){dp[i+1][0] += (dp[i][0])*j;if(i>0) dp[i+1][0] += j;if(i>0) dp[i+1][1] = dp[i][1]*j;else dp[i+1][1] = j;}else{dp[i+1][0] += (dp[i][0])*j;if(i>0) dp[i+1][0] += j;}}// prarr(dp);pr(dp[n][0] + dp[n][1]);return 0;}