結果
問題 | No.1407 Kindness |
ユーザー |
![]() |
提出日時 | 2021-02-27 10:28:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 5,040 bytes |
コンパイル時間 | 1,161 ms |
コンパイル使用メモリ | 118,544 KB |
最終ジャッジ日時 | 2025-01-19 07:45:12 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <iostream>#include <algorithm>#include <map>#include <set>#include <queue>#include <bitset>#include <climits>#include <cmath>#include <complex>#include <functional>#include <cassert>#include <stack>#include <numeric>#include <iomanip>#include <limits>typedef int64_t ll;typedef std::pair<int, int> Pii;typedef std::pair<ll, ll> Pll;typedef std::pair<double, double> Pdd;#define rip(_i, _n, _s) for (int _i = (_s); _i < (int)(_n); _i++)#define all(_l) _l.begin(), _l.end()#define rall(_l) _l.rbegin(), _l.rend()#define MM << " " <<template<typename _T>using MaxHeap = std::priority_queue<_T>;template<typename _T>using MinHeap = std::priority_queue<_T, std::vector<_T>, std::greater<_T>>;template<typename _T>inline bool chmax(_T &_l, const _T _b) {if (_l < _b) {_l = _b;return true;}return false;}template<typename _T>inline bool chmin(_T &_l, const _T _b) {if (_l > _b) {_l = _b;return true;}return false;}# ifdef LOCAL_DEBUGtemplate<typename _T>void vdeb(const std::vector<_T> &bb) {for (unsigned int i = 0;i < bb.size();i++) {if (i == bb.size() - 1) std::cout << bb[i];else std::cout << bb[i] << ' ';}std::cout << '\n';}template<typename _T>void vdeb(const std::vector<std::vector<_T>> &bb) {for (unsigned int i = 0;i < bb.size();i++) {std::cout << i << ' ';vdeb(bb[i]);}std::cout << '\n';}# endiflong long pow(long long n, long long p, long long k) {//n^k(mod p)if (!k) return 1;long long a = pow(n,p, k>>1);a = a * a%p;if (k & 1) a = a * n%p;return a;}void euclid(long long &a, long long &b, long long p) { // a>=b A*b+B*(a-a/b*b)=1if (a == 1) {a = 1;}else {long long A = b, B = a % b;euclid(A, B, p);b = (A - (p + a / b) % p * B % p + p) % p;a = B;}}long long rev(long long n, long long p) {// n*x-p*y=1//long long q = p;//euclid(p, n, p);//return n % q;return pow(n,p,p-2);}long long bino(long long n, long long m, long long p) {//nCm(mod p)long long ans = 1, div = 1;for(int i = 0;i < m; i++){ans = (n - i) * ans % p;div = div * (i +1) % p;}return ans * rev(div, p) % p;}struct modint {long long num;long long p;modint() {num = 0;p = 1000000007;}modint(long long x) {p = 1000000007;num = x % p;}modint inv()const{return rev(num, p);}modint operator-() const{return modint(p-num);}modint& operator+=(const modint &other){num = (num + other.num) % p;return *this;}modint& operator-=(const modint &other){num = (num - other.num + p) % p;return *this;}modint& operator*=(const modint &other){num = (num * other.num) % p;return *this;}modint& operator/=(const modint &other){(*this) *= other.inv();return *this;}modint& operator+=(const long long &other){num = (num + other) % p;return *this;}modint& operator-=(const long long &other){num = (num - other + p) % p;return *this;}modint& operator*=(const long long &other){num = (num * other) % p;return *this;}modint& operator/=(const long long &other){(*this) *= rev(other, p);return *this;}modint& operator++(){return *this += 1;}modint& operator--(){return *this -= 1;}modint& operator=(const long long &other){return (*this) = modint(other);}modint operator+(const modint &other) const{return modint(*this) += other;}modint operator-(const modint &other) const{return modint(*this) -= other;}modint operator*(const modint &other) const{return modint(*this) *= other;}modint operator/(const modint &other) const{return modint(*this) /= other;}modint operator+(const long long &other) const{return modint(*this) += other;}modint operator-(const long long &other) const{return modint(*this) -= other;}modint operator*(const long long &other) const{return modint(*this) *= other;}modint operator/(const long long &other) const{return modint(*this) /= other;}bool operator==(const modint &other) const{return num == other.num;}};std::istream& operator>>(std::istream &is, const modint x) {std::cin >> x.num;return is;}std::ostream& operator<<(std::ostream &os, const modint &x){std::cout << x.num;return os;}using namespace std;int main() {string s; cin >> s;vector<modint> da(10);rip(i,10,1) {da[i] = da[i-1] + i;}int n = s.size();vector<modint> dd(n);dd[0] += 1;modint ans, now(1);rip(i,n,1) {dd[i] = dd[i-1] * da[9];ans += dd[i];}rip(i,n,0) {ans += now * da[max(0, s[i]-'1')] * dd[n-i-1];now *= s[i]-'0';}ans += now;cout << ans << endl;}