QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#447341#6954. Almost AcyclicAcoippWA 3171ms154884kbC++143.4kb2024-06-18 10:11:462024-06-18 10:11:46

Judging History

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

  • [2024-06-18 10:11:46]
  • 评测
  • 测评结果:WA
  • 用时:3171ms
  • 内存:154884kb
  • [2024-06-18 10:11:46]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll T,n,i,j,val[17][17],a[17][17],tr,cir[17],ans1,ans2,ans,f[1<<17][17][17],id[17],g[1<<17],h[1<<17],h2[1<<17];
inline ll calc(ll x){return x*(x-1)/2;}
inline ll qmi(ll a,ll b,ll p){
	ll res = 1%p,t = a;
	while(b){
		if(b&1) res=res*t%p;
		t=t*t%p;
		b>>=1;
	}
	return res;
}
inline ll solve_tree(ll n){
	ll has=0,i,j,k,ans=1,res;
	for(i=1;i<n;i++) for(j=1;j<n;j++) a[i][j]=(a[i][j]%mod+mod)%mod;
	for(i=1;i<n;i++){
		for(j=i+1;j<n;j++){
			if(a[j][i]){
				swap(a[i],a[j]),has^=1;
				break;
			}
		}
		ll inv = qmi(a[i][i],mod-2,mod);
		for(j=1;j<n;j++){
			if(i==j) continue;
			ll res = a[j][i]*inv%mod;
			for(k=i;k<n;k++) a[j][k]=(a[j][k]-a[i][k]*res%mod+mod)%mod;
		}
	}
	if(i<n){
		cout<<0<<endl;
		return 0;
	}
	for(i=1;i<n;i++) ans=ans*a[i][i]%mod;
	if(has) ans=(mod-ans)%mod;
	return ans;
}
inline ll solve_ans1(){
	ll ans = 0;
	for(ll i=1;i<(1<<n);i++){
		memset(id,0,sizeof(id));
		ll tot = 0;
		for(ll j=0;j<n;j++) if(((i>>j)&1)) id[j+1]=++tot;
		memset(a,0,sizeof(a));
		for(ll j=1;j<=n;j++){
			for(ll k=j+1;k<=n;k++){
				if(!id[j]||!id[k]) continue;
				a[id[j]][id[k]]-=val[j][k];
				a[id[k]][id[j]]-=val[j][k];
				a[id[j]][id[j]]+=val[j][k];
				a[id[k]][id[k]]+=val[j][k];
			}
		}
		g[i]=solve_tree(tot);
	}
	for(ll i=1;i<=n;i++){
		for(ll j=0;j<(1<<n);j++){
			h[j]=0;
			ll res=1;
			for(ll k=0;k<n;k++) if((j>>k)&1) res=res*(1+val[k+1][i])%mod;
			res=(res-1+mod)%mod;
			h2[j]=g[j]*res%mod;
		}
		h[0]=1;
		for(ll j=1;j<(1<<n);j++){
			ll up = (j&(-j));
			for(ll k=j-up;;k=((j-up)&(k-1))){
				h[j]=(h[j]+h[j-(k|up)]*h2[k|up])%mod;
				if(k==0) break;
			}
		}
		ans=(ans+h[(1<<n)-1-(1<<i-1)])%mod;
	} 
	return ans;
}
inline ll solve_ans2(){
	ll ans = 0;
	
	return ans;
}
inline void solve_cir(){
	for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++) for(ll k=0;k<(1<<n);k++) f[k][i][j]=0;
	for(ll i=1;i<=n;i++) f[1<<i-1][i][i]=1;
	for(ll i=1;i<(1<<n);i++){
		ll res = 0,cnt = __builtin_popcount(i),tot = 0;
		if(cnt<=2) goto end;
		for(ll j=0;j<n;j++){
			for(ll k=0;k<n;k++){
				if(j!=k&&((i>>j)&1)&&((i>>k)&1)) res=(res+f[i][j+1][k+1]*val[j+1][k+1])%mod; 
			}
		}
		res = res*qmi(2*cnt,mod-2,mod)%mod;
		memset(a,0,sizeof(a));
		for(ll j=0;j<n;j++){
			if(!((i>>j)&1)) id[j+1]=++tot;
			else id[j+1]=n-cnt+1;
		}
		for(ll j=1;j<=n;j++){
			for(ll k=j+1;k<=n;k++){
				a[id[j]][id[k]]-=val[j][k];
				a[id[k]][id[j]]-=val[j][k];
				a[id[j]][id[j]]+=val[j][k];
				a[id[k]][id[k]]+=val[j][k];
			}
		}
		cir[cnt] = (cir[cnt]+res*solve_tree(n-cnt+1))%mod;
		end:;
		for(ll j=0;j<n;j++) for(ll k=0;k<n;k++) for(ll l=0;l<n;l++) if(!((i>>l)&1)&&((i>>j)&1)&&((i>>k)&1)) f[i|(1<<l)][j+1][l+1]=(f[i|(1<<l)][j+1][l+1]+f[i][j+1][k+1]*val[k+1][l+1])%mod;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--){
		memset(cir,0,sizeof(cir));
		memset(a,0,sizeof(a));
		cin>>n;
		for(i=1;i<=n;i++) for(j=1;j<=n;j++) cin>>val[i][j];
		if(n==1){
			cout<<1<<endl;
			continue;
		}
		for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) a[i][i]+=val[i][j],a[j][j]+=val[i][j],a[i][j]-=val[i][j],a[j][i]-=val[i][j];
		tr = solve_tree(n);
		ans1 = solve_ans1();
		ans2 = solve_ans2();
		solve_cir();
		ans = ans1-ans2+tr*(calc(n)-n+1)%mod;
		for(i=1;i<=n;i++) ans+=cir[i]*(calc(i)-i+1)%mod;
		cout<<(ans%mod+mod)%mod<<endl;
	}
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 3171ms
memory: 154884kb

input:

16
1
0
2
0 953763239
953763239 0
3
0 734999893 771971068
734999893 0 980773372
771971068 980773372 0
4
0 295218414 142837698 715328025
295218414 0 833169030 224028769
142837698 833169030 0 450275651
715328025 224028769 450275651 0
5
0 168127828 27116722 242318695 817220009
168127828 0 719973784 3288...

output:

1
907526471
435648763
45382643
853476025
217965230
310972283
249043356
720070307
956533032
727899419
765446998
5862363
820054147
570149010
531019608

result:

wrong answer 2nd lines differ - expected: '953763239', found: '907526471'