結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
![]() |
提出日時 | 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 second using 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; else ret *= x; } if (p != -1) x = (x * x) % p; else x *= 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; }