結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
|
提出日時 | 2021-03-05 23:18:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 34 ms / 3,000 ms |
コード長 | 4,674 bytes |
コンパイル時間 | 2,140 ms |
コンパイル使用メモリ | 204,340 KB |
最終ジャッジ日時 | 2025-01-19 11:59:02 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,n) for(ll i=0;i<n;i++)#define repl(i,l,r) for(ll i=(l);i<(r);i++)#define per(i,n) for(ll i=(n)-1;i>=0;i--)#define perl(i,r,l) for(ll i=r-1;i>=l;i--)#define fi first#define se second#define pb push_back#define ins insert#define pqueue(x) priority_queue<x,vector<x>,greater<x>>#define all(x) (x).begin(),(x).end()#define CST(x) cout<<fixed<<setprecision(x)#define rev(x) reverse(x);using ll=long long;using vl=vector<ll>;using vvl=vector<vector<ll>>;using pl=pair<ll,ll>;using vpl=vector<pl>;using vvpl=vector<vpl>;const ll MOD=1000000007;const ll MOD9=998244353;const int inf=1e9+10;const ll INF=4e18;const ll dy[8]={-1,0,1,0,1,1,-1,-1};const ll dx[8]={0,-1,0,1,1,-1,1,-1};template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}const int mod = 1000000007;const int max_n = 200005;struct mint {ll x; // typedef long long ll;mint(ll x=0):x((x%mod+mod)%mod){}mint operator-() const { return mint(-x);}mint& operator+=(const mint a) {if ((x += a.x) >= mod) x -= mod;return *this;}mint& operator-=(const mint a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}mint operator+(const mint a) const { return mint(*this) += a;}mint operator-(const mint a) const { return mint(*this) -= a;}mint operator*(const mint a) const { return mint(*this) *= a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}bool operator==(const mint &p) const { return x == p.x; }bool operator!=(const mint &p) const { return x != p.x; }// for prime modmint inv() const { return pow(mod-2);}mint& operator/=(const mint a) { return *this *= a.inv();}mint operator/(const mint a) const { return mint(*this) /= a;}};istream& operator>>(istream& is, mint& a) { return is >> a.x;}ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}mint calc(string s){vector<vector<vector<mint>>> dp(s.size()+1,vector<vector<mint>>(9,vector<mint>(2)));dp[0][0][0]=1;rep(i,s.size()){ll p=s[i]-'0';rep(j,9){if(p==0){}else if(p==5){dp[i+1][min(j/3+1,2LL)*3+j%3][0]+=dp[i][j][0];}else if(p==4||p==8){dp[i+1][j-(j%3)+min(j%3+2,2LL)][0]+=dp[i][j][0];}else if(p==2||p==6){dp[i+1][j-(j%3)+min(j%3+1,2LL)][0]+=dp[i][j][0];}else{dp[i+1][j][0]+=dp[i][j][0];}}rep(j,9){for(int p=1;p<=9;p++){if(p==0){}else if(p==5){dp[i+1][min(j/3+1,2LL)*3+j%3][1]+=dp[i][j][1];}else if(p==4||p==8){dp[i+1][j-(j%3)+min(j%3+2,2LL)][1]+=dp[i][j][1];}else if(p==2||p==6){dp[i+1][j-(j%3)+min(j%3+1,2LL)][1]+=dp[i][j][1];}else{dp[i+1][j][1]+=dp[i][j][1];}}}ll t=p;rep(j,9){for(int p=1;p<t;p++){if(p==0){}else if(p==5){dp[i+1][min(j/3+1,2LL)*3+j%3][1]+=dp[i][j][0];}else if(p==4||p==8){dp[i+1][j-(j%3)+min(j%3+2,2LL)][1]+=dp[i][j][0];}else if(p==2||p==6){dp[i+1][j-(j%3)+min(j%3+1,2LL)][1]+=dp[i][j][0];}else{dp[i+1][j][1]+=dp[i][j][0];}}}}mint ans=0;ans+=dp[s.size()][8][0]+dp[s.size()][8][1];return ans;}mint dp[10010][9];int main(){rep(i,10010)rep(j,9)dp[i][j]=0;dp[0][0]=1;string s;cin >> s;rep(i,10002){rep(j,9){dp[i+1][min(j/3+1,2LL)*3+j%3]+=dp[i][j];dp[i+1][j-(j%3)+min(j%3+2,2LL)]+=dp[i][j]*2;dp[i+1][j-(j%3)+min(j%3+1,2LL)]+=dp[i][j]*2;dp[i+1][j]+=dp[i][j]*4;}}mint ans=0;//string t;rep(i,s.size()-1){//t+='9';//ans+=calc(t);ans+=dp[i+1][8];//cout << ans <<endl;}ans+=calc(s);cout <<ans <<endl;}