結果
問題 | No.1050 Zero (Maximum) |
ユーザー |
![]() |
提出日時 | 2020-05-08 22:18:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 63 ms / 2,000 ms |
コード長 | 1,574 bytes |
コンパイル時間 | 1,607 ms |
コンパイル使用メモリ | 174,772 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-04 00:52:28 |
合計ジャッジ時間 | 2,611 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;} template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;} typedef vector<ll> vec; typedef vector<vec> mat; ll mod=1e9+7; mat mul(mat &a,mat&b){ mat c(a.size(),vec(b[0].size())); for (int i = 0; i < a.size(); i++){ for (int k = 0; k < b.size(); k++){ for (int j = 0; j < b[0].size(); j++){ c[i][j]=(c[i][j] + a[i][k] * b[k][j]) %mod; } } } return c; } mat matpow(mat a,ll m){ mat b(a.size(),vec(a.size())); for (int i = 0; i < a.size(); i++){ b[i][i]=1; } while(m>0){ if(m&1) b=mul(b,a); a=mul(a,a); m>>=1; } return b; } ll calc(mat A, ll m){ A = matpow(A,m); return A[0][0]; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); /* // めっちゃ雑にやることを考える int dp[k][m]={}; dp[0][0]=1; // O(k*m^2) for(int i=0;i<k;i++){ for(int j=0;j<m;j++){ for(int t=0;t<m;t++){ dp[i+1][(j+t)%m] += dp[i][j]; dp[i+1][(j*t)%m] += dp[i][t]; } } } */ ll k,m; cin>>m>>k; mat A(m,vec(m)); for(int i=0;i<m;i++){ for(int j=0;j<m;j++){ A[(i+j)%m][i]++; A[(i*j)%m][i]++; } } ll ans = calc(A,k); cout << ans << endl; }