QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#419378 | #8702. 狼人杀 | Williamxzh# | 23 | 2599ms | 10076kb | C++23 | 1.7kb | 2024-05-23 21:07:50 | 2024-05-23 21:07:51 |
Judging History
answer
#include <bits/stdc++.h>
#define il inline
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
il ll qp(ll a,ll b){
ll ans=1ll;
while(b){
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod,b>>=1;
}return ans;
}
il void add(ll &x,ll y){x=(x+y>=mod?x+y-mod:x+y);}
il void del(ll &x,ll y){x=(x<y?x-y+mod:x-y);}
il int pc(int x){
int s=0;
while(x) ++s,x-=(x&-x);
return s;
}
const int N=20;
ll f[1<<N],a[1<<N],inv[(N+2)*(N+2)];int b[N],to[N],c[N][N];
il int get(int l,int r){return l?((1<<(r+1))-(1<<l)):(1<<(r+1))-1;}
il ll solve(int n,int u,int v){//u:wolf,v:predictor
if(n==2) return 0ll;
int S=(1<<(n-1)),x=0,y,z,mul=(n*(n+1ll))/2ll;ll w,ret=0ll;
for(int i=0;i<n;++i){
if(i==v) continue;
b[x]=i,to[i]=x,++x;
}
for(int i=0;i<n;++i){
c[i][i]=(1<<to[i])*(i!=v);
for(int j=i+1;j<n;++j){
c[i][j]=c[i][j-1]+(1<<to[j])*(j!=v);
}
}
for(int i=0;i<S;++i) f[i]=0ll;
f[1<<to[u]]=0ll;
for(int i=(1<<to[u])+1;i<S;++i){
if(!((i>>to[u])&1)) continue;
y=0,w=0ll;
for(int l=0;l<n;++l)
for(int r=l;r<n;++r){
x=c[l][r];if(u<l || u>r) x=S-1-x;
x&=i;if(x==i) ++y;else add(w,f[x]);
}
//w=(w+(mul-y)*inv[mul])%mod;printf("%d %d %lld\n",i,y,w);
f[i]=((w+mul)*inv[mul-y])%mod;
}
return f[S-1];
}
int n,m;ll ans;
il void init(){
inv[0]=1ll;
for(int i=1;i<=n*n;++i) inv[i]=qp(i,mod-2ll);
}
int main(){
scanf("%d%d",&n,&m);init();
for(int i=1;i<=n;++i) if(i!=m) ans=(ans+solve(n,m-1,i-1))%mod;
printf("%lld",(ans*qp(n-1ll,mod-2ll))%mod);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 23
Accepted
Test #1:
score: 23
Accepted
time: 3ms
memory: 5920kb
input:
12 2
output:
183756997
result:
ok single line: '183756997'
Test #2:
score: 23
Accepted
time: 136ms
memory: 5844kb
input:
17 6
output:
97571903
result:
ok single line: '97571903'
Test #3:
score: 23
Accepted
time: 5ms
memory: 5884kb
input:
13 3
output:
209826617
result:
ok single line: '209826617'
Test #4:
score: 23
Accepted
time: 2ms
memory: 5980kb
input:
13 8
output:
176038768
result:
ok single line: '176038768'
Test #5:
score: 23
Accepted
time: 309ms
memory: 6044kb
input:
18 4
output:
288404061
result:
ok single line: '288404061'
Test #6:
score: 23
Accepted
time: 1ms
memory: 5836kb
input:
10 10
output:
219657163
result:
ok single line: '219657163'
Test #7:
score: 23
Accepted
time: 713ms
memory: 7892kb
input:
19 15
output:
590577825
result:
ok single line: '590577825'
Test #8:
score: 23
Accepted
time: 2ms
memory: 5900kb
input:
11 6
output:
488143489
result:
ok single line: '488143489'
Test #9:
score: 23
Accepted
time: 0ms
memory: 5892kb
input:
10 5
output:
470594541
result:
ok single line: '470594541'
Test #10:
score: 23
Accepted
time: 1647ms
memory: 10076kb
input:
20 5
output:
582458555
result:
ok single line: '582458555'
Test #11:
score: 23
Accepted
time: 1600ms
memory: 9940kb
input:
20 12
output:
648081410
result:
ok single line: '648081410'
Test #12:
score: 23
Accepted
time: 1643ms
memory: 9936kb
input:
20 4
output:
335777285
result:
ok single line: '335777285'
Test #13:
score: 23
Accepted
time: 1609ms
memory: 10072kb
input:
20 15
output:
389216500
result:
ok single line: '389216500'
Test #14:
score: 23
Accepted
time: 1639ms
memory: 10076kb
input:
20 16
output:
582458555
result:
ok single line: '582458555'
Test #15:
score: 23
Accepted
time: 1645ms
memory: 10076kb
input:
20 19
output:
589126150
result:
ok single line: '589126150'
Test #16:
score: 23
Accepted
time: 1602ms
memory: 10076kb
input:
20 6
output:
389216500
result:
ok single line: '389216500'
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #17:
score: 0
Wrong Answer
time: 2599ms
memory: 6000kb
input:
49 14
output:
475811538
result:
wrong answer 1st lines differ - expected: '486918542', found: '475811538'
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%