結果
問題 | No.1706 Many Bus Stops (hard) |
ユーザー |
|
提出日時 | 2021-10-08 22:29:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,088 bytes |
コンパイル時間 | 594 ms |
コンパイル使用メモリ | 69,864 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-23 05:12:51 |
合計ジャッジ時間 | 1,886 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
コンパイルメッセージ
main.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 35 | main() | ^~~~
ソースコード
#include<iostream>#include<atcoder/modint>using namespace std;using mint=atcoder::modint1000000007;#include<array>template<typename T,unsigned int N>struct Matrix{array<array<T,N>,N>dat;array<T,N>&operator[](int i){return dat[i];}const array<T,N>&operator[](int i)const{return dat[i];}static Matrix eye(){Matrix res;for(int i=0;i<N;i++)res[i][i]=1;return res;}Matrix operator+(const Matrix&A)const{Matrix res;for(int i=0;i<N;i++)for(int j=0;j<N;j++)res[i][j]=dat[i][j]+A[i][j];return res;}Matrix operator*(const Matrix&A)const{Matrix res;for(int i=0;i<N;i++)for(int k=0;k<N;k++)for(int j=0;j<N;j++)res[i][j]+=dat[i][k]*A[k][j];return res;}Matrix pow(long long n)const{Matrix a=*this,res=eye();for(;n;a=a*a,n>>=1)if(n&1)res=res*a;return res;}};using mat=Matrix<mint,4>;main(){int C,N,M;cin>>C>>N>>M;const mint inv=mint(1)/C;mat A;for(int i=2;i<4;i++)A[i-2][i]=1;A[0][0]=inv;A[3][0]=(C-1)*inv;A[1][1]=inv;A[2][1]=inv;A[3][1]=(C-2)*inv;A=A.pow(N);cout<<(1-(1-A[0][0]).pow(M)).val()<<endl;}