QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#416183 | #8702. 狼人杀 | cqbzly | 57 | 293ms | 11372kb | C++14 | 1.9kb | 2024-05-21 16:59:19 | 2024-05-21 16:59:19 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N=55;
const int mod=1e9+7;
int n,m;
ll f[N][N*N][N],ifac[N*N],res;
int get(int x){
return x*(x+1)/2;
}
ll fpow(ll x,ll y=mod-2){
ll z(1);
for(;y;y>>=1){
if(y&1)z=z*x%mod;
x=x*x%mod;
}return z;
}
void init(int n){
ifac[1]=1;for(int i=2;i<=n;i++)ifac[i]=mod-ifac[mod%i]*(mod/i)%mod;
}
int main(){
//freopen("data.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m,init(n*(n+1));
if(n==2){
cout<<0;
return 0;
}
f[0][0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=i*(i+1)/2;j++){
for(int k=0;k<=i;k++){
if(!f[i][j][k])continue;
for(int l=i+1;l<=n;l++){
(f[l][j+get(l-i-1)][k+1]-=f[i][j][k])%=mod;
}
}
}
}
for(int i=0;i<=n-m;i++){
for(int j=0;j<=i*(i+1)/2;j++){
for(int k=0;k<=i;k++){
if(!f[i][j][k])continue;
for(int ti=0;ti<=m-1;ti++){
for(int tj=0;tj<=ti*(ti+1)/2;tj++){
for(int tk=0;tk<=ti;tk++){
if(!f[ti][tj][tk])continue;
int x=(n-m-i+1)*(m-1-ti+1)+j+tj+get(n-m-i)+get(m-1-ti);
int y=n*(n+1)/2-x;
if(!y)continue;
//cout<<"find:"<<i<<" "<<j<<" "<<k<<" "<<ti<<" "<<tj<<" "<<tk<<" "<<y<<" "<<f[i][j][k]*f[ti][tj][tk]<<"\n";
res=(res-f[i][j][k]*f[ti][tj][tk]%mod*ifac[y]%mod*(n-1-k-tk))%mod;
}
}
}
}
}
}
res=res*fpow(n-1)%mod*n*(n+1)%mod*(mod+1>>1)%mod;
cout<<(res+mod)%mod;
}
詳細信息
Subtask #1:
score: 23
Accepted
Test #1:
score: 23
Accepted
time: 1ms
memory: 3776kb
input:
12 2
output:
183756997
result:
ok single line: '183756997'
Test #2:
score: 23
Accepted
time: 1ms
memory: 3972kb
input:
17 6
output:
97571903
result:
ok single line: '97571903'
Test #3:
score: 23
Accepted
time: 1ms
memory: 3784kb
input:
13 3
output:
209826617
result:
ok single line: '209826617'
Test #4:
score: 23
Accepted
time: 1ms
memory: 3736kb
input:
13 8
output:
176038768
result:
ok single line: '176038768'
Test #5:
score: 23
Accepted
time: 1ms
memory: 4060kb
input:
18 4
output:
288404061
result:
ok single line: '288404061'
Test #6:
score: 23
Accepted
time: 0ms
memory: 3684kb
input:
10 10
output:
219657163
result:
ok single line: '219657163'
Test #7:
score: 23
Accepted
time: 1ms
memory: 4052kb
input:
19 15
output:
590577825
result:
ok single line: '590577825'
Test #8:
score: 23
Accepted
time: 1ms
memory: 3644kb
input:
11 6
output:
488143489
result:
ok single line: '488143489'
Test #9:
score: 23
Accepted
time: 1ms
memory: 3752kb
input:
10 5
output:
470594541
result:
ok single line: '470594541'
Test #10:
score: 23
Accepted
time: 0ms
memory: 4104kb
input:
20 5
output:
582458555
result:
ok single line: '582458555'
Test #11:
score: 23
Accepted
time: 2ms
memory: 4236kb
input:
20 12
output:
648081410
result:
ok single line: '648081410'
Test #12:
score: 23
Accepted
time: 1ms
memory: 4128kb
input:
20 4
output:
335777285
result:
ok single line: '335777285'
Test #13:
score: 23
Accepted
time: 0ms
memory: 4128kb
input:
20 15
output:
389216500
result:
ok single line: '389216500'
Test #14:
score: 23
Accepted
time: 1ms
memory: 4128kb
input:
20 16
output:
582458555
result:
ok single line: '582458555'
Test #15:
score: 23
Accepted
time: 0ms
memory: 4112kb
input:
20 19
output:
589126150
result:
ok single line: '589126150'
Test #16:
score: 23
Accepted
time: 0ms
memory: 4116kb
input:
20 6
output:
389216500
result:
ok single line: '389216500'
Subtask #2:
score: 34
Accepted
Dependency #1:
100%
Accepted
Test #17:
score: 34
Accepted
time: 108ms
memory: 10844kb
input:
49 14
output:
486918542
result:
ok single line: '486918542'
Test #18:
score: 34
Accepted
time: 4ms
memory: 7048kb
input:
28 13
output:
642223597
result:
ok single line: '642223597'
Test #19:
score: 34
Accepted
time: 13ms
memory: 6236kb
input:
35 23
output:
842346505
result:
ok single line: '842346505'
Test #20:
score: 34
Accepted
time: 48ms
memory: 10076kb
input:
47 11
output:
583647040
result:
ok single line: '583647040'
Test #21:
score: 34
Accepted
time: 5ms
memory: 6020kb
input:
34 30
output:
990970048
result:
ok single line: '990970048'
Test #22:
score: 34
Accepted
time: 3ms
memory: 5408kb
input:
30 7
output:
393675971
result:
ok single line: '393675971'
Test #23:
score: 34
Accepted
time: 6ms
memory: 8544kb
input:
43 5
output:
737421246
result:
ok single line: '737421246'
Test #24:
score: 34
Accepted
time: 0ms
memory: 5280kb
input:
30 21
output:
254760745
result:
ok single line: '254760745'
Test #25:
score: 34
Accepted
time: 2ms
memory: 4980kb
input:
27 22
output:
266692865
result:
ok single line: '266692865'
Test #26:
score: 34
Accepted
time: 25ms
memory: 7580kb
input:
40 12
output:
133652311
result:
ok single line: '133652311'
Test #27:
score: 34
Accepted
time: 0ms
memory: 5252kb
input:
29 4
output:
873892090
result:
ok single line: '873892090'
Test #28:
score: 34
Accepted
time: 12ms
memory: 11340kb
input:
50 46
output:
267950067
result:
ok single line: '267950067'
Test #29:
score: 34
Accepted
time: 65ms
memory: 11372kb
input:
50 11
output:
423642322
result:
ok single line: '423642322'
Test #30:
score: 34
Accepted
time: 33ms
memory: 11260kb
input:
50 43
output:
625476642
result:
ok single line: '625476642'
Test #31:
score: 34
Accepted
time: 152ms
memory: 11336kb
input:
50 36
output:
767166129
result:
ok single line: '767166129'
Test #32:
score: 34
Accepted
time: 125ms
memory: 11248kb
input:
50 14
output:
357467965
result:
ok single line: '357467965'
Test #33:
score: 34
Accepted
time: 293ms
memory: 11256kb
input:
50 30
output:
219673347
result:
ok single line: '219673347'
Test #34:
score: 34
Accepted
time: 32ms
memory: 11304kb
input:
50 44
output:
392786132
result:
ok single line: '392786132'
Test #35:
score: 34
Accepted
time: 53ms
memory: 11236kb
input:
50 10
output:
848251616
result:
ok single line: '848251616'
Subtask #3:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #36:
score: 0
Runtime Error
input:
75 47