結果
| 問題 | No.1417 100の倍数かつ正整数(2) |
| ユーザー |
 tanimani364
|
| 提出日時 | 2021-04-16 18:32:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 34 ms / 3,000 ms |
| コード長 | 4,906 bytes |
| コンパイル時間 | 2,900 ms |
| コンパイル使用メモリ | 198,920 KB |
| 最終ジャッジ日時 | 2025-01-20 18:16:36 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
#include <bits/stdc++.h>//#include<boost/multiprecision/cpp_int.hpp>//#include<boost/multiprecision/cpp_dec_float.hpp>//#include <atcoder/all>#define rep(i, a) for (int i = (int)0; i < (int)a; ++i)#define rrep(i, a) for (int i = (int)a; i >-1; --i)#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)#define RREP(i, a, b) for (int i = (int)a; i > b; --i)#define repl(i, a) for (ll i = (ll)0; i < (ll)a; ++i)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define popcount __builtin_popcount#define popcountll __builtin_popcountll#define fi first#define se secondusing ll = long long;constexpr ll mod = 1e9 + 7;constexpr ll mod_998244353 = 998244353;constexpr ll INF = 1LL << 60;// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")//using lll=boost::multiprecision::cpp_int;//using Double=boost::multiprecision::number<boost::multiprecision::cpp_dec_float<128>>;//仮数部が1024桁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;}ll mypow(ll x, ll n, const ll &p = -1){ //x^nをmodで割った余りif (p != -1){x =(x%p+p)%p;}ll ret = 1;while (n > 0){if (n & 1){if (p != -1)ret = (ret * x) % p;elseret *= x;}if (p != -1)x = (x * x) % p;elsex *= x;n >>= 1;}return ret;}using namespace std;//using namespace atcoder;template<int mod>struct Modint{int x;Modint():x(0){}Modint(int64_t y):x((y%mod+mod)%mod){}Modint &operator+=(const Modint &p){if((x+=p.x)>=mod)x -= mod;return *this;}Modint &operator-=(const Modint &p){if((x+=mod-p.x)>=mod)x -= mod;return *this;}Modint &operator*=(const Modint &p){x = (1LL * x * p.x) % mod;return *this;}Modint &operator/=(const Modint &p){*this *= p.inverse();return *this;}Modint operator-() const { return Modint(-x); }Modint operator+(const Modint &p) const{return Modint(*this) += p;}Modint operator-(const Modint &p) const{return Modint(*this) -= p;}Modint operator*(const Modint &p) const{return Modint(*this) *= p;}Modint operator/(const Modint &p) const{return Modint(*this) /= p;}bool operator==(const Modint &p) const { return x == p.x; }bool operator!=(const Modint &p) const{return x != p.x;}Modint inverse() const{//非再帰拡張ユークリッドint a = x, b = mod, u = 1, v = 0;while(b>0){int t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return Modint(u);}Modint pow(int64_t n) const{//繰り返し二乗法Modint ret(1), mul(x);while(n>0){if(n&1)ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os,const Modint &p){return os << p.x;}};using modint = Modint<mod>;using modint2= Modint<mod_998244353>;modint dp[100005][2][3][3][2];void solve(){string s;cin>>s;int n=s.size();rep(i,n+1)rep(j,2)rep(k,3)rep(a,3)rep(z,2)dp[i][j][k][a][z]=0;dp[0][0][0][0][1]=1;rep(i,n){rep(j,2){//真に小さいかどうかrep(two,3){rep(five,3){rep(leading_zero,2){if(!j){rep(d,10){if(s[i]-'0'<d)continue;if(!leading_zero&&!d)continue;if(d==8)dp[i+1][s[i]-'0'>d][min(2,two+3)][five][0]+=dp[i][0][two][five][leading_zero];else if(d==4)dp[i+1][s[i]-'0'>d][min(2,two+2)][five][0]+=dp[i][0][two][five][leading_zero];else if(d==2||d==6)dp[i+1][s[i]-'0'>d][min(2,two+1)][five][0]+=dp[i][0][two][five][leading_zero];else if(d==5)dp[i+1][s[i]-'0'>d][two][min(2,five+1)][0]+=dp[i][0][two][five][leading_zero];else if(!d)dp[i+1][s[i]-'0'>d][two][five][leading_zero]+=dp[i][0][two][five][leading_zero];else dp[i+1][s[i]-'0'>d][two][five][0]+=dp[i][0][two][five][leading_zero];}}else{dp[i+1][1][min(2,two+3)][five][0]+=dp[i][1][two][five][leading_zero];dp[i+1][1][min(2,two+2)][five][0]+=dp[i][1][two][five][leading_zero];rep(x,2)dp[i+1][1][min(2,two+1)][five][0]+=dp[i][1][two][five][leading_zero];dp[i+1][1][two][min(2,five+1)][0]+=dp[i][1][two][five][leading_zero];rep(d,10){if((d>0&&d%2==0)||d==5)continue;if(!leading_zero&&!d)continue;if(!d)dp[i+1][1][two][five][leading_zero]+=dp[i][1][two][five][leading_zero];else dp[i+1][1][two][five][0]+=dp[i][1][two][five][leading_zero];}}}}}}}modint ans=0;rep(i,2)ans+=dp[n][i][2][2][0];cout<<ans<<"\n";}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout << fixed << setprecision(15);solve();return 0;}