結果
問題 | No.1407 Kindness |
ユーザー |
![]() |
提出日時 | 2021-02-26 21:35:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 2,766 bytes |
コンパイル時間 | 1,771 ms |
コンパイル使用メモリ | 174,172 KB |
実行使用メモリ | 18,176 KB |
最終ジャッジ日時 | 2024-10-02 14:09:16 |
合計ジャッジ時間 | 3,002 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2021.02.26 21:35:29**/#include "bits/stdc++.h"using namespace std;typedef long long ll;template< int MOD >struct mint {public:long long x;mint(long long x = 0) :x((x%MOD+MOD)%MOD) {}mint(std::string &s) {long long z = 0;for (int i = 0; i < s.size(); i++) {z *= 10;z += s[i] - '0';z %= MOD;}this->x = z;}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) {long long n = MOD - 2;mint u = 1, b = a;while (n > 0) {if (n & 1) {u *= b;}b *= b;n >>= 1;}return *this *= u;}mint operator+(const mint &a) const {mint res(*this);return res += a;}mint operator-() const {return mint() -= *this; }mint operator-(const mint &a) const {mint res(*this);return res -= a;}mint operator*(const mint &a) const {mint res(*this);return res *= a;}mint operator/(const mint &a) const {mint res(*this);return res /= a;}friend std::ostream& operator<<(std::ostream &os, const mint &n) {return os << n.x;}friend std::istream &operator>>(std::istream &is, mint &n) {long long x;is >> x;n = mint(x);return is;}bool operator==(const mint &a) const {return this->x == a.x;}bool operator!=(const mint &a) const {return this->x != a.x;}mint pow(long long k) const {mint ret = 1;mint p = this->x;while (k > 0) {if (k & 1) {ret *= p;}p *= p;k >>= 1;}return ret;}};constexpr int MOD = 1e9 + 7;int main() {string s;cin >> s;vector<vector<vector<mint<MOD>>>> dp(s.size()+1,vector<vector<mint<MOD>>>(2,vector<mint<MOD>>(2,0)));dp[0][0][0] = 1;for (int i = 0; i < s.size(); i++) {for (int j = 1; j < s[i]-'0'; j++) {dp[i+1][1][1] += (dp[i][0][0] + dp[i][0][1]) * j;}dp[i+1][1][0] = 1;dp[i+1][1][1] += (dp[i][1][0] + dp[i][1][1]) * 45;dp[i+1][0][1] += (dp[i][0][0] + dp[i][0][1]) * (s[i]-'0');}cout << dp[s.size()][0][0] + dp[s.size()][0][1] + dp[s.size()][1][1] << endl;return 0;}