結果
問題 | No.741 AscNumber(Easy) |
ユーザー |
![]() |
提出日時 | 2019-09-19 22:10:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 460 ms / 2,000 ms |
コード長 | 2,584 bytes |
コンパイル時間 | 1,409 ms |
コンパイル使用メモリ | 168,228 KB |
実行使用メモリ | 183,344 KB |
最終ジャッジ日時 | 2024-07-20 17:41:09 |
合計ジャッジ時間 | 12,851 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
#include <bits/stdc++.h>const int INF = 1e9;const int MOD = 1e9 + 7;const long long LINF = 1e18;#define dump(x) cout << 'x' << ' = ' << (x) << ` `;#define FOR(i, a, b) for(int i = (a); i < (b); ++i)#define rep(i, n) for(int i = 0; i < (n); ++i)#define REPR(i, n) for(int i = n; i >= 0; i--)#define FOREACH(x, a) for(auto &(x) : (a))typedef long long ll;using namespace std;typedef pair<ll, ll> P;template <std::uint_fast64_t Modulus> class modint {using u64 = std::uint_fast64_t;public:u64 a;constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}constexpr u64 &value() noexcept { return a; }constexpr const u64 &value() const noexcept { return a; }constexpr modint operator+(const modint rhs) const noexcept {return modint(*this) += rhs;}constexpr modint operator-(const modint rhs) const noexcept {return modint(*this) -= rhs;}constexpr modint operator*(const modint rhs) const noexcept {return modint(*this) *= rhs;}constexpr modint operator/(const modint rhs) const noexcept {return modint(*this) /= rhs;}constexpr modint &operator+=(const modint rhs) noexcept {a += rhs.a;if(a >= Modulus) {a -= Modulus;}return *this;}constexpr modint &operator-=(const modint rhs) noexcept {if(a < rhs.a) {a += Modulus;}a -= rhs.a;return *this;}constexpr modint &operator*=(const modint rhs) noexcept {a = a * rhs.a % Modulus;return *this;}constexpr modint &operator/=(modint rhs) noexcept {u64 exp = Modulus - 2;while(exp) {if(exp % 2) {*this *= rhs;}rhs *= rhs;exp /= 2;}return *this;}};using mint = modint<MOD>;constexpr int M = 1145141;mint dp[M][2][10];int main(int argc, char const *argv[]) {int a; cin>>a;string s = "1";rep(i,a) s.push_back('0');int n = s.length();rep(i,M) rep(j,2) rep(k,10) dp[i][j][k] = 0;dp[0][0][0] = 1;rep(i,n) {int D = (int)(s[i]-'0');rep(j,2) {for (int x = 0; x <= (j?9:D); ++x) {rep(k,10) {if (x < k) continue;dp[i+1][j||(x<D)][x] += dp[i][j][k];}}}}mint ans = 0;rep(j,2) {rep(k,10) {ans += dp[n][j][k];}}cout << ans.a << endl;return 0;}