結果
問題 | No.1815 K色問題 |
ユーザー | okkuukenken |
提出日時 | 2020-01-09 19:14:52 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,631 bytes |
コンパイル時間 | 972 ms |
コンパイル使用メモリ | 82,408 KB |
実行使用メモリ | 6,676 KB |
最終ジャッジ日時 | 2024-03-13 11:29:29 |
合計ジャッジ時間 | 2,732 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | AC | 88 ms
6,676 KB |
testcase_10 | AC | 50 ms
6,676 KB |
testcase_11 | AC | 75 ms
6,676 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
ソースコード
#include<iostream> #include<vector> #define int long long using namespace std; constexpr int mod=1e9+7; int pow(int x,int n){ int res=1; while(n){ if(n&1) (res*=x)%=mod; (x*=x)%=mod; n>>=1; } return res; } int inv(int n){ return pow(n,mod-2); } int fact[100001]; int mod_fact(int n){ if(fact[n]!=0) return fact[n]; if(n==0) return fact[n]=1; return fact[n]=n*mod_fact(n-1)%mod; } int comb(int n,int k){ return mod_fact(n)*inv(mod_fact(k)*mod_fact(n-k)%mod)%mod; } typedef vector<int>vec; typedef vector<vec>mat; 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]+=a[i][k]*b[k][j])%=mod; return c; } mat pow_mat(mat a,int n){ mat b(a.size(),vec(a.size())); for(int i=0;i<a.size();i++) b[i][i]=1; while(n){ if(n&1) b=mul(b,a); a=mul(a,a); n>>=1; } return b; } signed main(){ int n,m; cin>>n>>m; int ans=m*(m-1)%mod; if(m&1) ans=mod-ans; for(int i=3;i<=m;i+=1){ mat a(1,vec(2)),b(2,vec(2)),c(2,vec(1)); a[0][0]=1,a[0][1]=1; b[0][0]=(i*i*i-i*i*6+i*14-13)%mod,b[0][1]=(i*i*i-i*i*6+i*13-10)%mod,b[1][0]=(i*i-i*4+5)%mod,b[1][1]=(i*i-i*3+3)%mod; c[0][0]=(i*i*i-i*i*3+i*2)%mod,c[1][0]=(i*i-i)%mod; int tmp=mul(mul(a,pow_mat(b,n-1)),c)[0][0]; (tmp*=comb(m,i))%=mod; if((m-i)&1) tmp=mod-tmp; (ans+=tmp)%=mod; } cout<<ans<<endl; }