QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#851902 | #8702. 狼人杀 | wanggiaoxing | 100 ✓ | 2046ms | 65108kb | C++14 | 1.4kb | 2025-01-11 08:48:15 | 2025-01-11 08:48:16 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
//#define int __int128
#define ll long long
#define pa pair<int,int>
//#define int unsigned long long
#define sg signed
#define fi first
#define se second
#define ls s[x][0]
#define rs s[x][1]
#define ld long double
#define bs basic_string
const int inf=1e18;
const int mod=1e9+7;
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n,m,dp[155][30005][2];
int get(int x){
return x*(x+1)/2;
}
int mi(int x,int y){
int ans=1,base=x;
while(y){
if(y&1)ans=(ans*base)%mod;
base=(base*base)%mod;
y>>=1;
}
return ans;
}
void solve(){
n=read(),m=read();
dp[0][0][0]=1;
for(int i=1;i<=n+1;i++){
if(i==m)continue;
for(int j=0;j<=n*n;j++)for(int k=0;k<i;k++){
for(int op:{0,1})dp[i][j+get(i-k-1)][op]=(dp[i][j+get(i-k-1)][op]-dp[k][j][op])%mod;
dp[i][j+get(i-k-1)][1]=(dp[i][j+get(i-k-1)][1]-dp[k][j][0]*(i-k-1-(k<m&&i>m)))%mod;
}
}
int ans=0;
for(int i=0;i<=n*n;i++){
// cout<<i<<" "<<dp[n+1][i][1]<<endl;
ans=(ans+dp[n+1][i][1]*mi((1-i*mi(get(n),mod-2))%mod,mod-2))%mod;
}
cout<<(ans*mi(n-1,mod-2)%mod+mod)%mod;
}
signed main(){
int t=1;while(t--)solve();
return 0;
}
詳細信息
Subtask #1:
score: 23
Accepted
Test #1:
score: 23
Accepted
time: 1ms
memory: 3780kb
input:
12 2
output:
183756997
result:
ok single line: '183756997'
Test #2:
score: 23
Accepted
time: 1ms
memory: 3728kb
input:
17 6
output:
97571903
result:
ok single line: '97571903'
Test #3:
score: 23
Accepted
time: 1ms
memory: 3728kb
input:
13 3
output:
209826617
result:
ok single line: '209826617'
Test #4:
score: 23
Accepted
time: 1ms
memory: 3660kb
input:
13 8
output:
176038768
result:
ok single line: '176038768'
Test #5:
score: 23
Accepted
time: 0ms
memory: 3804kb
input:
18 4
output:
288404061
result:
ok single line: '288404061'
Test #6:
score: 23
Accepted
time: 0ms
memory: 3616kb
input:
10 10
output:
219657163
result:
ok single line: '219657163'
Test #7:
score: 23
Accepted
time: 1ms
memory: 3872kb
input:
19 15
output:
590577825
result:
ok single line: '590577825'
Test #8:
score: 23
Accepted
time: 0ms
memory: 3700kb
input:
11 6
output:
488143489
result:
ok single line: '488143489'
Test #9:
score: 23
Accepted
time: 0ms
memory: 3760kb
input:
10 5
output:
470594541
result:
ok single line: '470594541'
Test #10:
score: 23
Accepted
time: 1ms
memory: 3872kb
input:
20 5
output:
582458555
result:
ok single line: '582458555'
Test #11:
score: 23
Accepted
time: 1ms
memory: 3784kb
input:
20 12
output:
648081410
result:
ok single line: '648081410'
Test #12:
score: 23
Accepted
time: 1ms
memory: 3776kb
input:
20 4
output:
335777285
result:
ok single line: '335777285'
Test #13:
score: 23
Accepted
time: 1ms
memory: 3768kb
input:
20 15
output:
389216500
result:
ok single line: '389216500'
Test #14:
score: 23
Accepted
time: 1ms
memory: 3800kb
input:
20 16
output:
582458555
result:
ok single line: '582458555'
Test #15:
score: 23
Accepted
time: 1ms
memory: 3864kb
input:
20 19
output:
589126150
result:
ok single line: '589126150'
Test #16:
score: 23
Accepted
time: 1ms
memory: 3868kb
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: 12ms
memory: 5928kb
input:
49 14
output:
486918542
result:
ok single line: '486918542'
Test #18:
score: 34
Accepted
time: 2ms
memory: 4216kb
input:
28 13
output:
642223597
result:
ok single line: '642223597'
Test #19:
score: 34
Accepted
time: 2ms
memory: 4636kb
input:
35 23
output:
842346505
result:
ok single line: '842346505'
Test #20:
score: 34
Accepted
time: 14ms
memory: 5648kb
input:
47 11
output:
583647040
result:
ok single line: '583647040'
Test #21:
score: 34
Accepted
time: 4ms
memory: 4496kb
input:
34 30
output:
990970048
result:
ok single line: '990970048'
Test #22:
score: 34
Accepted
time: 3ms
memory: 4240kb
input:
30 7
output:
393675971
result:
ok single line: '393675971'
Test #23:
score: 34
Accepted
time: 10ms
memory: 5332kb
input:
43 5
output:
737421246
result:
ok single line: '737421246'
Test #24:
score: 34
Accepted
time: 3ms
memory: 4244kb
input:
30 21
output:
254760745
result:
ok single line: '254760745'
Test #25:
score: 34
Accepted
time: 0ms
memory: 4092kb
input:
27 22
output:
266692865
result:
ok single line: '266692865'
Test #26:
score: 34
Accepted
time: 8ms
memory: 4956kb
input:
40 12
output:
133652311
result:
ok single line: '133652311'
Test #27:
score: 34
Accepted
time: 0ms
memory: 4076kb
input:
29 4
output:
873892090
result:
ok single line: '873892090'
Test #28:
score: 34
Accepted
time: 18ms
memory: 6128kb
input:
50 46
output:
267950067
result:
ok single line: '267950067'
Test #29:
score: 34
Accepted
time: 18ms
memory: 6196kb
input:
50 11
output:
423642322
result:
ok single line: '423642322'
Test #30:
score: 34
Accepted
time: 14ms
memory: 6056kb
input:
50 43
output:
625476642
result:
ok single line: '625476642'
Test #31:
score: 34
Accepted
time: 18ms
memory: 6004kb
input:
50 36
output:
767166129
result:
ok single line: '767166129'
Test #32:
score: 34
Accepted
time: 14ms
memory: 6136kb
input:
50 14
output:
357467965
result:
ok single line: '357467965'
Test #33:
score: 34
Accepted
time: 14ms
memory: 6144kb
input:
50 30
output:
219673347
result:
ok single line: '219673347'
Test #34:
score: 34
Accepted
time: 18ms
memory: 6112kb
input:
50 44
output:
392786132
result:
ok single line: '392786132'
Test #35:
score: 34
Accepted
time: 18ms
memory: 5988kb
input:
50 10
output:
848251616
result:
ok single line: '848251616'
Subtask #3:
score: 43
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #36:
score: 43
Accepted
time: 84ms
memory: 11644kb
input:
75 47
output:
668751416
result:
ok single line: '668751416'
Test #37:
score: 43
Accepted
time: 86ms
memory: 11532kb
input:
75 41
output:
310834114
result:
ok single line: '310834114'
Test #38:
score: 43
Accepted
time: 1065ms
memory: 47088kb
input:
133 124
output:
57167600
result:
ok single line: '57167600'
Test #39:
score: 43
Accepted
time: 925ms
memory: 43312kb
input:
129 74
output:
751074385
result:
ok single line: '751074385'
Test #40:
score: 43
Accepted
time: 1077ms
memory: 49024kb
input:
135 133
output:
759430862
result:
ok single line: '759430862'
Test #41:
score: 43
Accepted
time: 89ms
memory: 11736kb
input:
75 19
output:
967921272
result:
ok single line: '967921272'
Test #42:
score: 43
Accepted
time: 722ms
memory: 39004kb
input:
124 9
output:
641081661
result:
ok single line: '641081661'
Test #43:
score: 43
Accepted
time: 80ms
memory: 11884kb
input:
76 66
output:
465902083
result:
ok single line: '465902083'
Test #44:
score: 43
Accepted
time: 1462ms
memory: 56612kb
input:
142 13
output:
12401929
result:
ok single line: '12401929'
Test #45:
score: 43
Accepted
time: 1944ms
memory: 65108kb
input:
150 5
output:
388058135
result:
ok single line: '388058135'
Test #46:
score: 43
Accepted
time: 400ms
memory: 27696kb
input:
109 97
output:
381109644
result:
ok single line: '381109644'
Test #47:
score: 43
Accepted
time: 1940ms
memory: 64880kb
input:
150 133
output:
174431234
result:
ok single line: '174431234'
Test #48:
score: 43
Accepted
time: 1883ms
memory: 64848kb
input:
150 147
output:
198921722
result:
ok single line: '198921722'
Test #49:
score: 43
Accepted
time: 1918ms
memory: 64996kb
input:
150 142
output:
631473185
result:
ok single line: '631473185'
Test #50:
score: 43
Accepted
time: 1910ms
memory: 65032kb
input:
150 136
output:
743180069
result:
ok single line: '743180069'
Test #51:
score: 43
Accepted
time: 1902ms
memory: 64832kb
input:
150 138
output:
621574340
result:
ok single line: '621574340'
Test #52:
score: 43
Accepted
time: 2046ms
memory: 64856kb
input:
150 119
output:
872660153
result:
ok single line: '872660153'
Test #53:
score: 43
Accepted
time: 1892ms
memory: 64884kb
input:
150 144
output:
939939060
result:
ok single line: '939939060'
Test #54:
score: 43
Accepted
time: 1831ms
memory: 64964kb
input:
150 1
output:
166208360
result:
ok single line: '166208360'
Test #55:
score: 43
Accepted
time: 1896ms
memory: 64864kb
input:
150 75
output:
353929212
result:
ok single line: '353929212'