結果
問題 | No.673 カブトムシ |
ユーザー | kopricky |
提出日時 | 2018-04-16 19:20:02 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 6,046 bytes |
コンパイル時間 | 1,554 ms |
コンパイル使用メモリ | 167,980 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 06:02:56 |
合計ジャッジ時間 | 2,442 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 1 ms
6,940 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 1 ms
6,940 KB |
testcase_10 | AC | 1 ms
6,944 KB |
testcase_11 | AC | 1 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 1 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 1 ms
6,944 KB |
testcase_16 | AC | 1 ms
6,944 KB |
testcase_17 | AC | 2 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl #define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl #define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl #define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl #define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl #define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl using namespace std; typedef pair<int,int> P; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<double> vd; typedef vector<P> vp; typedef vector<string> vs; const int MAX_N = 100005; // powかmod_powかはその都度変更する // 係数の順番に注意する!!! // A[n] = 3*A[n-1]+2*A[n-2] とかなら a は {2,3} となる template<typename T> class mat : public vector<vector<T> > { private: int r,c; //行,列 public: int row() const { return r; } int column() const { return c; } mat(int n,int m,T val = 0){ this->r = n,this->c = m; rep(i,n){ this->push_back(vector<T>(m,val)); } } mat operator+(const mat& another){ if(this->r != another.r && this->c != another.c){ cout << "足し算失敗(サイズ不一致)" << endl; exit(1); } mat<T> X(this->r,this->c); rep(i,this->r){ rep(j,this->c){ X[i][j] = (*this)[i][j] + another[i][j]; } } return X; } mat operator+(const T val){ mat<T> X(this->r,this->c); rep(i,this->r){ rep(j,this->c){ X[i][j] = (*this)[i][j] + val; } } return X; } mat operator-(const mat& another){ if(this->r != another.r && this->c != another.c){ cout << "引き算失敗(サイズ不一致)" << endl; exit(1); } mat<T> X(this->r,this->c); rep(i,this->r){ rep(j,this->c){ X[i][j] = (*this)[i][j] - another[i][j]; } } return X; } mat operator-(const T val){ mat<T> X(this->r,this->c); rep(i,this->r){ rep(j,this->c){ X[i][j] = (*this)[i][j] - val; } } return X; } vector<T> operator*(const vector<T>& another){ if(this->c != (int)another.size()){ cout << "掛け算失敗(サイズ不一致)" << endl; exit(1); } vector<T> vec(this->r,0); rep(i,this->r){ rep(j,this->c){ vec[i] += (*this)[i][j] * another[j]; } } return vec; } mat operator*(const mat& another){ if(this->c != another.r){ cout << "掛け算失敗(サイズ不一致)" << endl; exit(1); } mat<T> X(this->r,another.c); rep(i,this->r){ rep(k,this->c){ rep(j,another.c){ X[i][j] += (*this)[i][k]*another[k][j]; } } } return X; } mat operator-(){ mat<T> X(this->r,this->c); rep(i,this->r){ rep(j,this->c){ X[i][j] = -(*this)[i][j]; } } return X; } void print(){ rep(i,this->r){ rep(j,(this->c)-1){ cout << (*this)[i][j] << ","; } cout << (*this)[i][(this->c)-1] << endl; } } }; template<typename T> mat<T> pow(mat<T> A,ll cnt) { if(A.row() != A.column()){ cout << "累乗不可" << endl; } int n = A.row(); mat<T> B(n,n); rep(i,n){ B[i][i] = 1; } while(cnt>0){ if(cnt & 1){ B = B*A; } A = A*A; cnt >>= 1; } return B; } template<typename T> mat<T> mod_mul(mat<T>& A,mat<T>& B) { if(A.column() != B.row()){ cout << "掛け算失敗(サイズ不一致)" << endl; exit(1); } mat<T> X(A.row(),B.column()); rep(i,A.row()){ rep(k,A.column()){ rep(j,B.column()){ X[i][j] = (X[i][j] + A[i][k]*B[k][j]) % MOD; } } } return X; } template<typename T> mat<T> mod_pow(mat<T> A,ll cnt) { if(A.row() != A.column()){ cout << "累乗不可" << endl; } int n = A.row(); mat<T> B(n,n); rep(i,n){ B[i][i] = 1; } while(cnt>0){ if(cnt & 1){ B = mod_mul(B,A); } A = mod_mul(A,A); cnt >>= 1; } return B; } // 第1引数 : A[n] = a[0] + a[1] * A[n-k] + a[2] * A[n-k+1] + ... + a[k] * A[n-1] // 第2引数 : A[0] = x[0], A[1] = x[1], ... , A[k-1] = x[k-1] template<typename T> T solve(vector<T>& a, vector<T>& x, ll n) { int k = (int)a.size() - 1; if(n < k){ return x[n]; } mat<T> A(k+1,k+1); rep(i,k+1){ A[0][i] = a[k-i]; } rep(i,k-1){ A[i+1][i] = 1; } A[k][k] = 1; mat<T> B = mod_pow(A,n-k+1); T res = 0; rep(i,k){ res = (res + B[0][i]*x[k-1-i]%MOD) % MOD; } res = (res + B[0][k]) % MOD; return res; } int main() { cin.tie(0); ios::sync_with_stdio(false); ll b,c,d; cin >> b >> c >> d; b %= MOD, c %= MOD, d; vl a = {b*c%MOD,c}, x = {0}; cout << solve<ll>(a,x,d) << "\n"; return 0; }