結果
問題 | No.793 うし数列 2 |
ユーザー |
![]() |
提出日時 | 2019-02-22 23:35:33 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,314 bytes |
コンパイル時間 | 1,146 ms |
コンパイル使用メモリ | 82,568 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-26 01:43:54 |
合計ジャッジ時間 | 1,620 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include<cstdio>#include<cstring>#include<vector>#include<queue>#include<stack>#include<algorithm>#include<cmath>#include<climits>#include<string>#include<set>#include<unordered_set>#include<numeric>#include<map>#include<iostream>using namespace std;#define rep(i,n) for(int i = 0;i<((int)(n));i++)#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)typedef long long ll;typedef pair<ll, ll> mp;ll mod = 1e9+7;ll inf = 1e18;ll n,ans;// 拡張ユークリッドの互除法// 返り値: a と b の最大公約数// ax + by = gcd(a, b) を満たす (x, y) が格納されるlong long extGCD(long long a, long long b, long long &x, long long &y) {if (b == 0) {x = 1;y = 0;return a;}long long d = extGCD(b, a%b, y, x);y -= a/b * x;return d;}ll invmod(ll a,ll m){ll x,y;extGCD(a,m,x,y);x%=m;if(x<0)x+=m;return x;}//累乗法ll mod_pow(ll x,ll n,ll mod=1e18+7){ll res=1;while(n){if(n&1) (res*=x)%=mod;(x*=x)%=mod;n>>=1;}return res;}int main(void){cin>>n;ll inv3 = invmod(3,mod);ans=(mod_pow(10,n,mod)*(1+inv3)) % mod;ans=(ans+mod-inv3) % mod;cout<<ans<<endl;return 0;}