結果
問題 | No.1706 Many Bus Stops (hard) |
ユーザー |
![]() |
提出日時 | 2021-09-11 01:36:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,707 bytes |
コンパイル時間 | 1,469 ms |
コンパイル使用メモリ | 80,732 KB |
最終ジャッジ日時 | 2025-01-24 12:37:21 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
#include <iostream> #include <vector> using namespace std; const long long mod=1000000007; vector<vector<long long>> matrix_mul(const vector<vector<long long>>& A,const vector<vector<long long>>&B){ vector<vector<long long>>C(A.size(),vector<long long>(B.at(0).size(),0)); for(int i=0;i<A.size();i++){ for(int k=0;k<B.size();k++){ for(int j=0;j<B.at(0).size();j++){ C.at(i).at(j)=(C.at(i).at(j)+A.at(i).at(k)*B.at(k).at(j))%mod; } } } return C; } vector<vector<long long>> matrix_exp(vector<vector<long long>> X,long long n){ vector<vector<long long>>Y(X.size(),vector<long long>(X.size(),0)); for(int i=0;i<X.size();i++){ Y.at(i).at(i)=1; } while(n>0){ if(n&1){ Y=matrix_mul(Y,X); } X=matrix_mul(X,X); n>>=1; } return Y; } long long calculate_nth(long long n,vector<vector<long long>> A,long long C){ A=matrix_exp(A,n); vector<vector<long long>> res; const vector<vector<long long>> b={ {1},{0},{C},{0} }; res=matrix_mul(A,b); return res.at(2).at(0); } long long mod_pow(long long x,long long n,long long m){ long long res=1; while(n>0){ if(n&1){ res=res*x%m; } x=x*x%m; n>>=1; } return res; } void safe_mod(long long& x,long long m){ while(x<0){ x+=m; } x%=m; return; } int main(){ long long C,N,M; cin>>C>>N>>M; const vector<vector<long long>>a={ {{1,0,0,1},{0,1,C-1,C-2},{C,0,0,0},{0,C,0,0}} }; long long ans,c,An,NAn,MNAn,MAn; ans=calculate_nth(N,a,C); c=mod_pow(mod_pow(C,mod-2,mod),N+1,mod); An=ans*c%mod; NAn=(1-An); safe_mod(NAn,mod); MNAn=mod_pow(NAn,M,mod); MAn=(1-MNAn); safe_mod(MAn,mod); cout<<MAn<<endl; return 0; }