結果
問題 | No.673 カブトムシ |
ユーザー | IL_msta |
提出日時 | 2018-04-13 23:30:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 15,657 bytes |
コンパイル時間 | 1,404 ms |
コンパイル使用メモリ | 126,820 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 05:54:27 |
合計ジャッジ時間 | 1,995 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
ソースコード
#define _USE_MATH_DEFINES#pragma region include#include <iostream>#include <iomanip>#include <stdio.h>#include <sstream>#include <algorithm>#include <iterator>#include <cmath>#include <complex>#include <string>#include <cstring>#include <vector>#include <bitset>#include <queue>#include <set>#include <map>#include <stack>#include <list>#include <ctime>//////#include <random>//#pragma endregion //#include/////////#pragma region typedeftypedef long long LL;typedef long double LD;typedef unsigned long long ULL;#pragma endregion //typedef////定数const int INF = (int)1e9;const LL MOD = (LL)1e9+7;const LL LINF = (LL)4e18+20;const LD PI = acos(-1.0);const double EPS = 1e-9;/////////using namespace::std;/////////#pragma region Math#pragma regionlong long ext_gcd(long long a,long long b,long long& x,long long& y){if(b==0){x=1;y=0;return a;}long long q = a/b;long long g = ext_gcd(b,a-q*b,x,y);x = x - q*y;swap(x,y);return g;}template<class T>inline T gcd(T a, T b){return b ? gcd(b, a % b) : a;}#pragma endregion // 最大公約数 gcd#pragma regiontemplate<class T>inline T lcm(T a, T b){return a / gcd(a, b) * b;}#pragma endregion // 最小公倍数 lcm#pragma regionlong long invMod(long long a,long long m=MOD){long long x,y;ext_gcd(a,m,x,y);x %= m;if(x<0) x += m;return x;}/*LL powMod(LL x,LL e,LL mod=MOD){LL prod = 1%mod;for(int i=63;i>=0;--i){prod = prod*prod % mod;if(e&1LL<<i)prod=prod*x%mod;}return prod;}*/LL powMod(LL num,LL n,LL mod=(LL)MOD){//(num**n)%modnum %= mod;//if( n == 0 ){return (LL)1;}LL mul = num;LL ans = (LL)1;while(n){if( n&1 ){ans = (ans*mul)%mod;}mul = (mul*mul)%mod;n >>= 1;}return ans;}/*LL mod_inverse(LL num,LL mod=MOD){return powMod(num,MOD-2,MOD);}*/#pragma endregion //繰り返し二乗法 powMod#pragma regiontemplate<class T>vector<T> getDivisor(T n){vector<T> v;for(int i=1;i*i<=n;++i){if( n%i == 0 ){v.push_back(i);if( i != n/i ){//平方数で重複して数えないようにv.push_back(n/i);}}}sort(v.begin(), v.end());return v;}#pragma endregion //約数列挙 getDivisor(n):O(√n)#pragma endregion //math//Utility:便利な奴#pragma regiontemplate<class T>void UNIQUE(vector<T>& vec){sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end() );}#pragma endregion // sort erase unique////////////////////////////////#pragma regionlong long bitcount64(long long bits){bits = (bits & 0x5555555555555555) + (bits >> 1 & 0x5555555555555555);bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333);bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f);bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff);bits = (bits & 0x0000ffff0000ffff) + (bits >>16 & 0x0000ffff0000ffff);return (bits & 0x00000000ffffffff) + (bits >>32 & 0x00000000ffffffff);}#pragma endregion //その他////////////////////////////////struct edge_base{int to;LL cost;};edge_base make_edge_base(int to,LL cost){edge_base ret = {to,cost};return ret;}#pragma region GRL#pragma region //グラフtemplate<class T,class EDGE>void dijkstra(int root,int V,vector<T>& dist,vector<int>& prev,vector< vector<EDGE> > G ){priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > > que;dist.assign(V,LINF);prev.assign(V,-1);dist[root] = 0;que.push(pair<T,int>(0,root));//距離、頂点番号while( !que.empty() ){pair<T,int> p = que.top();que.pop();int v = p.second;if( dist[v] < p.first ) continue;for(int i=0;i < (int)G[v].size();++i){EDGE e = G[v][i];if( dist[e.to] > dist[v] + e.cost ){dist[e.to] = dist[v] + e.cost;prev[e.to] = v;que.push(pair<T,int>(dist[e.to],e.to));}}}}//経路復元,dijkstraにprev入れた//http://ronly.hatenablog.com/entry/2017/06/17/161641vector<int> get_path(vector<int>& prev,int t){vector<int> path;while(t!=-1){path.push_back( t );t = prev[t];}reverse(path.begin(),path.end());return path;}#pragma endregion //ダイクストラ法:O(|E|log|V|)#pragma region //グラフvoid warshall_floyd(vector<vector<LL> >& dist,int V,const LL inf=LINF){for(int k=0;k<V;++k){for(int i=0;i<V;++i){if( dist[i][k] >= inf ) continue;for(int j=0;j<V;++j){if( dist[k][j] >= inf )continue;dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);}}}}#pragma endregion //ワーシャルフロイド:O(|V|**3)#pragma regionnamespace FLOW{//vector< vector<FLOW:edge> > G;struct edge_flow : public edge_base{LL cap;//LD cap;//int rev;};edge_flow make_edge_flow(int to,LL cap,int rev,LL cost=1){//edge_flow make_edge_flow(int to,LD cap,int rev,LL cost=1){edge_flow ret;ret.to = to;ret.cost = cost;ret.cap = cap;ret.rev = rev;return ret;}//*class Graph{public:int V;vector< vector<FLOW::edge_flow> > G;vector< LL > dist;vector< int > iter;vector< bool > used;void init(int v){V = v;G.resize(V);}void reset(){iter.assign(V,0);used.assign(V,false);}//directed graphvoid add_edge(int from,int to,LL cap){G[from].push_back( FLOW::make_edge_flow(to,cap,G[to].size()) );G[to].push_back( FLOW::make_edge_flow(from,0,G[from].size()-1) );}private://sから最短距離をBFSで計算するvoid bfs(int s){//許容量もチェックしているqueue<int> que;dist = vector<LL>(V,-1);dist[s] = 0;que.push(s);while(!que.empty()){int v = que.front();que.pop();for(int i=0;i<(int)G[v].size();++i){edge_flow &e = G[v][i];if( e.cap > 0 && dist[e.to] < 0 ){dist[e.to] = dist[v] + 1;que.push(e.to);}}}}private://増加パスをDFSで探すLL dfs(int v,int t,LL f){if( v==t ) return f;for(int &i = iter[v];i<(int)G[v].size();++i){//?FLOW::edge_flow &e = G[v][i];if( e.cap>0 && dist[v] < dist[e.to]){LL d = this->dfs(e.to, t, min(f,e.cap) );if( d > 0){e.cap -= d;G[e.to][e.rev].cap += d;return d;}}}return 0;}public://sからtへの最大流量を求めるLL max_flow(int s,int t){LL flow = 0;for(;;){this->bfs(s);if( dist[t] < 0 ) return flow;iter = vector<int>(V,0);LL f = this->dfs(s,t,LINF);do{flow += f;f = this->dfs(s,t,LINF);}while( f > 0 );}}};//*/}#pragma endregion //dinic :O(|E||V|^2)#pragma region //グラフbool is_bipartite(int v,int c,vector< vector<int> >& G,vector<int>& Color){Color[v] = c;for(int i=0;i < (int)G[v].size();++i){//隣接グラフif(Color[ G[v][i] ] == c ) return false;if(Color[ G[v][i] ] == 0 &&!is_bipartite(G[v][i],-c,G,Color)){return false;}}return true;}bool is_bipartite(int Root,vector< vector<int> >& Graph){int GraphSize = Graph.size();vector<int> Color(GraphSize,0);const int ColorNo = 1;return is_bipartite(Root,ColorNo,Graph,Color);}#pragma endregion //二部グラフチェック is_bipartite(root,GraphList)#pragma regionnamespace matching{//https://beta.atcoder.jp/contests/soundhound2018/tasks/soundhound2018_cint V; //頂点数vector< vector<int> > G;//グラフvector<int> match;//match[i]:頂点[i]がどことマッチされているかvector<bool > used;//void add_edge(int u,int v){G[u].push_back(v);G[v].push_back(u);}bool dfs(int v){/*https://mathtrain.jp/bipartitematching未マッチ辺・マッチ辺・未マッチ辺これをマッチ辺・未マッチ辺・マッチ辺に変えると1マッチが2マッチになる。未[済未]増加路を求めている。*/used[v] = true;//dfsのroot前に初期化されるint size = G[v].size();for(int i=0;i<size;++i){int u = G[v][i];//int w = match[u];//if( w<0 || ((used[w]==false) && dfs(w)) ){/*マッチングされていない||使われてない&&*/match[v] = u;match[u] = v;return true;}}return false;}int bipartite_matching(){int res = 0;match = vector<int>(V,-1);//未マッチ状態に初期化for(int v=0;v<V;++v){if( match[v] < 0 ){used = vector<bool>(V,false);if( dfs(v) ){++res;}}}return res;}}#pragma endregion //二部グラフの最大マッチング bipartite_matching()#pragma endregion //#pragma regionvector< vector<LL> > NCK;//初期値:0//http://sugarknri.hatenablog.com/entry/2016/07/16/165715void makeinv(vector<LL>& inv,const LL P){int i;//const int varMAX = max(100000,(int)inv.size());const int varMAX = max(300010,(int)inv.size());inv = vector<LL>( varMAX+1,0);inv[1]=1;for(i=2;i<=varMAX;i++){inv[i] = (inv[P%i] * (P-P/i)%P ) % P;//OVF//inv[i] = powMod(i,P-2,P);}}LL nCk(LL N,LL k,LL mod = MOD){static vector<LL> inv;//modの逆元if( inv.size() == 0 ){makeinv(inv,mod);//modは素数を入れる}k = min(k,N-k);if( k < 0 || k > N){return 0;}if( k == 0 ){return 1;}if( k == 1 ){return N%mod;}LL ret = 1;for(int i=1;i<=k;++i){ret = (ret * ((N+1-i)%mod) )%mod;//ret*N:OVFret = (ret * inv[i] )%mod;}return ret;}LL nCk_once(LL N,LL k,LL mod = MOD){//modは素数k = min(k,N-k);if( k < 0 || k > N ){return 0;}if( k == 0 ){return 1;}if( k == 1 ){return N%mod;}LL ret = 1;LL A=1;for(LL i=0;i<k;++i){A = (A * ((N-i)%mod) ) % mod;}LL B=1;for(LL i=2;i<=k;++i){B = (B * (i%mod) ) % mod;}ret = ( A * powMod(B,mod-2,mod) ) % mod;return ret;}#pragma endregion //組み合わせnCk(,10^5)#pragma regionLL nCk_base(int N,int K,LL mod=MOD){if( K<0 || N < K ) return 0;//多く取り過ぎK = min(K,N-K);if( K==0 ){return 1%mod;}if( K==1 ){return N%mod;}//%MOD;if( N<=10000 && NCK[N][K] ){return NCK[N][K];}//N個目を使わない:nCk(N-1,k)//N個目を使う :nCk(N-1,k-1)LL ans = (nCk_base(N-1,K)+nCk_base(N-1,K-1) )%mod;//%MOD;if( N<=10000 ){NCK[N][K] = ans;}return ans;}#pragma endregion //組み合わせ メモ?#pragma region DSLclass UnionFind{public:int cNum;//要素数vector<int> parent;vector<int> count;vector< vector<int> > GList;UnionFind(int n){cNum = n;parent = vector<int>(n);count = vector<int>(n,1);GList.resize(n);for(int i=0;i<n;++i){parent[i] = i;GList[i].push_back(i);}}int find(int x){if( parent[x] == x ){return x;}return parent[x] = find( parent[x] );}bool same(int x,int y){return find(x) == find(y);}int Count(int x){return count[find(x)];}void add(int x,int y){//unionx = find(x);y = find(y);if( x==y )return;parent[x] = y;count[y] += count[x];if( GList[y].size() < GList[x].size() ){swap(GList[x],GList[y]);}GList[y].insert( GList[y].end(),GList[x].begin(),GList[x].end() );}};#pragma endregion //UnionFind#pragma region DSLclass BITree{//1-indexint N;vector<LL> bit;public:BITree(int n){N = n;bit = vector<LL>(N+1,0);//1-index}void add(int a,LL w){//aにwを足すif( a <= 0 || N < a) return;//a:[1,N]for(int i=a;i<=N;i += i & -i){bit[i] += w;}}LL sum(int a){//[1,a]の和,a:[1,N]/*1番目からa番目までの和、1-index*/LL ret = 0;if( a > N ) a = N;for(int i=a; i > 0; i -= i & -i){ret += bit[i];}return ret;}};#pragma endregion //BIndexTree#pragma regiontemplate <typename T>class segment_base{int N;//要素数vector< T > dat1;T VAL_E;//初期値T VAL_NULL;//空の値public:segment_base(){};segment_base(int n,T val_E ):N(n),VAL_E(val_E){dat1.resize(2*n);dat1.assign(2*n,val_E);//初期化}void init(int n,T val_E,T val_N){N = n;VAL_E = val_E;VAL_NULL = val_N;int size = 2;while(size<N){size<<1;}N = size;dat1.resize(2*N);dat1.assign(2*N,val_E);}T SELECT(T& L,T& R){//扱う演算子T ans;ans = min(L,R);//return ans;}//index番目の値をvalに変更,indexは"0-index"void update(int i,T& val){i += N-1;dat1[i] = val;while(i>0){i = (i-1)/2;dat1[i] = SELECT(dat1[i*2+1],dat1[i*2+2]);}}//区間[L,R)のSELECT/*調べている範囲[a,b),階数k,見る場所[L,R)*/T query(int a,int b,int k,int L,int R){if( R<=a || b<=L ){return VAL_E;//交差しない}if( a<=L && R<=b && dat1[k] != VAL_NULL ){return dat1[k];}T res = VAL_E;int mid = (L+R)/2;if( a < mid ) res = SELECT(res,query(a,b,k*2+1,L,mid) );if( mid < b ) res = SELECT(res,query(a,b,k*2+2,mid,R) );return res;}T query(int L,int R){return query(L,R,0,0,N);}};#pragma endregion //segment_tree#pragma region//行列の積namespace mymat{LL matMOD = MOD;//初期値10^9 + 7};template<class T>vector< vector<T> > operator*( vector<vector<T> >& A,vector< vector<T> >& B){LL mod = mymat::matMOD;int R = A.size();int cen = A[0].size();int C = B[0].size();vector< vector<T> > ans(R,vector<T>(C,0) );for(int row=0;row<R;++row){for(int col=0;col<C;++col){for(int inner=0;inner< cen;++inner){/*ans[row][col] = (ans[row][col] + A[row][inner]*B[inner][col])%mod;//ans[row][col] = (ans[row][col] + A[row][inner]*B[inner][col]);ans[row][col] = (ans[row][col] + mod) % mod;//負になるときの処理*/ans[row][col] = (ans[row][col] + A[row][inner]*B[inner][col])%mod;}}}return ans;}template<class T>vector< vector<T> > powMod(const vector< vector<T> >& mat,LL N,LL mod=MOD){mymat::matMOD = mod;int R = mat.size();int C = mat[0].size();//R==Cvector< vector<T> > I(R,vector<T>(C,0));//単位元for(int i=0;i<R && i<C;++i){I[i][i] = 1;}if( N == 0 ){return I;}vector< vector<T> > mul(R,vector<T>(C)),ans(R,vector<T>(C));ans = I;mul = mat;while(N){if( N & 1 ){ans = ans*mul;}N >>= 1;mul = mul*mul;}return ans;}#pragma endregion //行列#pragma region#include<time.h>namespace TIME{clock_t start,end;void time_start(){start = clock();}void time_set(int t){end = start + t;}bool check(){return clock() < end;}/*unsigned long long get_cycle(){return __rdtsc();}unsigned long long start,limit;void time_start(){start = get_cycle();}//あたいをーさぐらないとーだめーvoid time_set(unsigned long long num){limit = num;}bool check(){return (get_cycle() < start+limit);}*/}#pragma endregion //時間計測#pragma regionnamespace RAND{unsigned long xor128(){static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;unsigned long t;t=(x^(x<<11));x=y;y=z;z=w;return( w=(w^(w>>19))^(t^(t>>8)) );}LL getRAND(LL P){return ((xor128()%P)+P)%P;}}#pragma endregion //乱数#pragma region#pragma endregion //////////////////////////void solve(){// 123456789//1000000007const LL mod = 1000000007;LL B,C,D;cin>>B>>C>>D;B %= mod;C %= mod;LL ans1 = (B*C)%mod;LL ans2 = (ans1+B)%mod;ans2 = (ans2*C) % mod;if(D==1){cout<<ans1<<endl;return;}else if(D==2){cout << ans2 << endl;return;}vector<vector<LL> > A(3,vector<LL>(3,0));A[0][0]=C;A[0][1]=0;A[0][2]=(B*C)%mod;A[1][0]=0;A[1][1]=C;A[1][2]=(B*C)%mod;A[2][0]=0;A[2][1]=0;A[2][2]=1;vector<vector<LL> > res;res = powMod(A,D-2,mod);vector<vector<LL> > X(3,vector<LL>(1));X[0][0]=ans2;X[1][0]=ans1;X[2][0]=1;vector<vector<LL> > ret;ret = res*X;cout << ret[0][0] << endl;}#pragma region mainsigned main(void){std::cin.tie(0);std::ios::sync_with_stdio(false);std::cout << std::fixed;//小数を10進数表示cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別solve();}#pragma endregion //main()