結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
|
提出日時 | 2025-01-01 01:20:58 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 3,000 ms |
コード長 | 3,190 bytes |
コンパイル時間 | 3,433 ms |
コンパイル使用メモリ | 256,360 KB |
実行使用メモリ | 9,472 KB |
最終ジャッジ日時 | 2025-01-01 01:21:07 |
合計ジャッジ時間 | 5,318 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<int m> struct StaticModint {using mint = StaticModint;int _v;constexpr StaticModint() : _v(0) {}template<class T>constexpr StaticModint(T v) : _v((v % m + m) % m) {}constexpr int val() const { return _v; }constexpr mint& operator ++ () { return *this += 1; }constexpr mint& operator -- () { return *this -= 1; }constexpr mint operator ++ (int) { mint res = *this; ++*this; return res; }constexpr mint operator -- (int) { mint res = *this; --*this; return res; }constexpr mint& operator += (const mint& r) {if(_v >= m - r._v) _v -= m;_v += r._v; return *this;}constexpr mint& operator -= (const mint& r) {if(_v < r._v) _v += m;_v -= r._v; return *this;}constexpr mint& operator *= (const mint& r) {unsigned long long z = _v;z *= r._v;_v = (unsigned int)(z % m); return *this;}constexpr mint& operator /= (const mint& r) {return *this *= r.inv();}constexpr mint pow(long long n) const {mint x = *this, r = 1;while(n) {if(n & 1) r *= x;x *= x;n >>= 1;}return r;}constexpr mint inv() const {return pow(m - 2);}constexpr mint operator + () const { return *this; }constexpr mint operator - () const { return mint() - *this; }constexpr mint operator + (const mint& r) const { return mint(*this) += r; }constexpr mint operator - (const mint& r) const { return mint(*this) -= r; }constexpr mint operator * (const mint& r) const { return mint(*this) *= r; }constexpr mint operator / (const mint& r) const { return mint(*this) /= r; }constexpr bool operator == (const mint& r) const { return _v == r._v; }constexpr bool operator != (const mint& r) const { return _v != r._v; }friend istream& operator >> (istream& is, mint& x) {long long t;is >> t;x = mint(t);return is;}friend ostream& operator << (ostream& os, const mint& x) {return os << x._v;}};// using mint = StaticModint<998244353>;using mint = StaticModint<1000000007>;int main() {cin.tie(nullptr);ios::sync_with_stdio(false);string S;cin >> S;int N = S.size();vector dp(N + 1, vector(3, vector(3, vector(2, mint(0)))));dp[0][0][0][0] = 1;for(int i = 0; i < N; i++) {// leading zerodp[i + 1][0][0][1] += 1;for(int j = 0; j < 3; j++) {for(int k = 0; k < 3; k++) {for(int l = 0; l < 2; l++) {for(int d = 1; d <= (l ? 9 : S[i] - '0'); d++) {int ni = i + 1;int nj = min(2, j + (d % 2 == 0) + (d % 4 == 0));int nk = min(2, k + (d == 5));int nl = l | d < S[i] - '0';dp[ni][nj][nk][nl] += dp[i][j][k][l];}}}}}cout << dp[N][2][2][0] + dp[N][2][2][1] << endl;return 0;}