結果
問題 | No.1050 Zero (Maximum) |
ユーザー |
|
提出日時 | 2020-05-08 21:51:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 662 bytes |
コンパイル時間 | 643 ms |
コンパイル使用メモリ | 65,792 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-04 00:30:47 |
合計ジャッジ時間 | 1,229 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
コンパイルメッセージ
main.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 6 | main() | ^~~~
ソースコード
#include<iostream>using namespace std;int M,K;const long mod=1e9+7;long E[50][50],A[50][50],T[50][50];main(){cin>>M>>K;for(int i=0;i<M;i++){for(int j=0;j<M;j++){A[(i+j)%M][i]++;A[i*j%M][i]++;}E[i][i]=1;}while(K){if(K&1){for(int i=0;i<M;i++)for(int j=0;j<M;j++)T[i][j]=E[i][j],E[i][j]=0;for(int i=0;i<M;i++)for(int j=0;j<M;j++){for(int k=0;k<M;k++)(E[i][j]+=T[i][k]*A[k][j])%=mod;}}K>>=1;for(int i=0;i<M;i++)for(int j=0;j<M;j++)T[i][j]=A[i][j],A[i][j]=0;for(int i=0;i<M;i++)for(int j=0;j<M;j++){for(int k=0;k<M;k++)(A[i][j]+=T[i][k]*T[k][j])%=mod;}}cout<<E[0][0]<<endl;}