結果
問題 | No.793 うし数列 2 |
ユーザー |
![]() |
提出日時 | 2019-02-22 22:11:45 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,497 bytes |
コンパイル時間 | 666 ms |
コンパイル使用メモリ | 92,536 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-25 08:50:30 |
合計ジャッジ時間 | 1,355 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include <cstdio>#include <cstdlib>#include <cmath>#include <climits>#include <cassert>#include <iostream>#include <iomanip>#include <string>#include <stack>#include <queue>#include <vector>#include <map>#include <set>#include <algorithm>#include <numeric>#include <bitset>#define all(c) c.begin(), c.end()#define rall(c) c.rbegin(), c.rend()#define debug(x) cerr << #x << ": " << x << endlusing namespace std;typedef long long ll;typedef pair<ll, ll> Pll;typedef pair<int, int> Pii;const ll MOD = 1000000007;const long double EPS = 1e-10;const int dyx[4][2] = {{ 0, 1}, {-1, 0}, {0,-1}, {1, 0}};map<ll, ll> memomodpow;ll modpow(ll a, ll t) {if(memomodpow[t]) return memomodpow[t];ll ret = 1LL;while(t) {if(t & 1) {ret *= a;ret %= MOD;}a *= a;a %= MOD;t >>= 1;}memomodpow[t] = ret;return ret;}map<ll, ll> memo;ll solve(ll ei) {if(memo[ei]) return memo[ei];if(ei <= 8) {ll ret = 0LL;for(int i=1;i<=ei;++i) {ret = ret * 10 + 3;}memo[ei] = ret;} else {ll l = solve(ei/2);ll r = solve((ei+1)/2);memo[ei] = ((l*modpow(10LL, (ei+1)/2))%MOD+r) % MOD;}return memo[ei];}int main() {ll ei;cin >> ei;if(ei <= 8) {cout << '1' + string(ei, '3') + "\n";} else {cout << (modpow(10LL, ei) + solve(ei))%MOD << "\n";}}