QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#419378#8702. 狼人杀Williamxzh#23 2599ms10076kbC++231.7kb2024-05-23 21:07:502024-05-23 21:07:51

Judging History

你现在查看的是最新测评结果

  • [2024-05-23 21:07:51]
  • 评测
  • 测评结果:23
  • 用时:2599ms
  • 内存:10076kb
  • [2024-05-23 21:07:50]
  • 提交

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%