QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#447341 | #6954. Almost Acyclic | Acoipp | WA | 3171ms | 154884kb | C++14 | 3.4kb | 2024-06-18 10:11:46 | 2024-06-18 10:11:46 |
Judging History
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'