結果
問題 | No.673 カブトムシ |
ユーザー | mugen_1337 |
提出日時 | 2020-07-16 09:57:31 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 6,375 bytes |
コンパイル時間 | 2,417 ms |
コンパイル使用メモリ | 209,604 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-03 07:47:34 |
合計ジャッジ時間 | 2,883 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 1 ms
5,376 KB |
testcase_16 | AC | 1 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define mod 1000000007 using ll=long long; const int INF=1000000000; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct IOSetup{ IOSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(12); } } iosetup; template<typename T1,typename T2> ostream &operator<<(ostream &os,const pair<T1,T2>&p){ os<<p.first<<" "<<p.second; return os; } template<typename T> ostream &operator<<(ostream &os,const vector<T>&v){ for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==v.size()?"":" "); return os; } template<ll Mod> struct ModInt{ long long x; ModInt():x(0){} ModInt(long long y):x(y>=0?y%Mod:(Mod-(-y)%Mod)%Mod){} ModInt &operator+=(const ModInt &p){ if((x+=p.x)>=Mod) x-=Mod; return *this; } ModInt &operator-=(const ModInt &p){ if((x+=Mod-p.x)>=Mod)x-=Mod; return *this; } ModInt &operator*=(const ModInt &p){ x=(int)(1ll*x*p.x%Mod); return *this; } ModInt &operator/=(const ModInt &p){ (*this)*=p.inverse(); return *this; } ModInt operator-()const{return ModInt(x);} ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;} ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;} ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;} ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;} ModInt operator==(const ModInt &p)const{return x==p.x;} ModInt operator!=(const ModInt &p)const{return x!=p.x;} ModInt inverse()const{ int a=x,b=Mod,u=1,v=0,t; while(b>0){ t=a/b; swap(a-=t*b,b);swap(u-=t*v,v); } return ModInt(u); } ModInt pow(long long n)const{ ModInt ret(1),mul(x); while(n>0){ if(n&1) ret*=mul; mul*=mul;n>>=1; } return ret; } friend ostream &operator<<(ostream &os,const ModInt &p){return os<<p.x;} friend istream &operator>>(istream &is,ModInt &a){long long t;is>>t;a=ModInt<Mod>(t);return (is);} static int get_mod(){return Mod;} }; using mint=ModInt<mod>; template<int MAX> struct comcalc{ vector<mint> fact,finv,inv; comcalc():fact(MAX),finv(MAX),inv(MAX){ fact[0]=mint(1),fact[1]=mint(1),finv[0]=mint(1),finv[1]=mint(1),inv[1]=mint(1); for(int i=2;i<MAX;i++){ fact[i]=fact[i-1]*mint(i); inv[i]=mint(0)-inv[mod%i]*(mint(mod/i)); finv[i]=finv[i-1]*inv[i]; } } mint com(int n,int k){ if(n<k) return mint(0); if(n<0 or k<0) return mint(0); return fact[n]*(finv[k]*finv[n-k]); } mint fac(int n){ return fact[n]; } // 重複組み合わせ:n種類の物から重複を許し,k個選ぶ mint nHk(int n,int k){ return com(n+k-1,k); } // 玉n区別,箱k区別,各箱1個以上O(k) mint F12_dis_dis_one(int n,int k){ mint ret=1; for(int i=0;i<=k;i++){ mint add=com(k,i)*(mint(i).pow(n)); if((k-i)%2) ret-=add; else ret+=add; } return ret; } }; mint pow_mod(mint x,ll n){ return x.pow(n); } mint inv_mod(mint x){ return x.inverse(); } // O(n) mint fact_mod(ll n){ mint ret=1; for(int i=2;i<=n;i++) ret*=mint(i); return ret; } // O(r) mint comb_mod(ll n,ll r){ if(r>n-r) r=n-r; if(r==0) return 1; mint a=1,b=mint(fact_mod(r)).inverse(); for(int i=0;i<r;i++)a*=mint(n-i); return a*b; } const int MAX=4010000; using cominit=comcalc<MAX>; template<class T> struct Matrix{ vector<vector<T>> A; Matrix(){} Matrix(int n,int m):A(n,vector<T>(m,T(0))){} Matrix(int n):A(n,vector<T>(n,T(0))){} int height()const{return (A.size());} int width()const{return (A[0].size());} inline const vector<T> &operator[](int k)const{return (A.at(k));} inline vector<T> &operator[](int k){return (A.at(k));} static Matrix I(int n){ Matrix mat(n); for(int i=0;i<n;i++)mat[i][i]=1; return (mat); } Matrix &operator+=(const Matrix &B){ int n=height(),m=width(); assert(n==B.height() and m==B.width()); for(int i=0;i<n;i++)for(int j=0;j<m;j++)(*this)[i][j]+=B[i][j]; return (*this); } Matrix &operator-=(const Matrix &B){ int n=height(),m=width(); assert(n==B.height() and m==B.width()); for(int i=0;i<n;i++)for(int j=0;j<m;j++)(*this)[i][j]-=B[i][j]; return (*this); } Matrix &operator*=(const Matrix &B){ int n=height(),m=B.width(),p=width(); assert(p==B.height()); vector<vector<T>> C(height(),vector<T>(B.width(),T(0))); for(int i=0;i<n;i++)for(int j=0;j<m;j++)for(int k=0;k<p;k++) C[i][j]=(C[i][j]+(*this)[i][k]*B[k][j]); swap(A,C); return (*this); } Matrix &operator^=(ll k){ Matrix res=Matrix::I(height()); while(k>0){ if(k&1) res*=(*this); (*this)*=(*this); k>>=1ll; } A.swap(res.A); return (*this); } Matrix operator+(const Matrix &B)const{return (Matrix(*this)+=B);} Matrix operator-(const Matrix &B)const{return (Matrix(*this)-=B);} Matrix operator*(const Matrix &B)const{return (Matrix(*this)*=B);} Matrix operator^(const long long k)const{return (Matrix(*this)^=k);} friend ostream &operator<<(ostream &os,Matrix &p){ for(int i=0;i<p.height();i++){ os<<"["; for(int j=0;j<p.width();j++) os<<p[i][j]<<(j+1==p.width()?"]\n":" "); } return os; } }; signed main(){ ll b,c,d;cin>>b>>c>>d; mint B=b,C=c; Matrix<mint> base(2); base[0][0]=C;base[0][1]=B*C; base[1][0]=0;base[1][1]=1; base^=d; Matrix<mint> a0(2,1); a0[0][0]=0; a0[1][0]=1; auto ans=base*a0; cout<<ans[0][0]<<endl; return 0; }