10%的数据,n ≤ 100, k = 0,w = 0。
直接输出即可。(就是个完全匹配)
10%的数据,n ≤ 10, k≤ 20, 0 ≤ w ≤ 500。
O(n!)枚举。(就是搜索啊~)
10%的数据,n≤ 15,k ≤ 20, 0 ≤ w ≤ 500。
状压,fi,j表示处理了左边前i个点,右边被匹配的点状态是j。
O(n * 2^n)。
10%的数据,n ≤ 100, k = 0, 0 ≤ w ≤ 500。
计算每个的贡献就好了。(可以试着打表找规律)
20%的数据,n≤ 100, k ≤ 15, 0 ≤ w ≤ 500。
容斥,枚举哪些边一定要选,然后计算每条边的贡献。
具体的实现可以看代码~
O(n* 2^k)。
其实这中题主要需要自己想明白,因为容斥千变万华~
#include <bits/stdc++.h> #pragma GCC optimize(2) #define p 1000000007 #define inc(i,a,b) for(register int i=a;i<=b;i++) using namespace std; int n,k; template<class nT> inline void read(nT& x) { char c; while(c=getchar(),!isdigit(c)); x=c^48; while(c=getchar(),isdigit(c)) x=x*10+c-48; } long long a[310][310],sumx[310],sumy[310]; long long sum; int l[310],r[310]; long long ans2,ans1; int bo[310]; long long f[310]; void dfs(int dep,int cnt,int ssum) { if(dep>=k){ long long tmp=sum; inc(i,1,cnt) tmp-=sumx[l[bo[i]]],tmp-=sumy[r[bo[i]]]; inc(i,1,cnt) inc(j,1,cnt) tmp+=a[l[bo[i]]][r[bo[j]]]; tmp=tmp*f[n-cnt-1]%p; tmp=(tmp+ssum*f[n-cnt]%p)%p; if(cnt&1) ans1=((ans1-f[n-cnt])%p+p)%p,ans2=((ans2-tmp)%p+p)%p; else ans1=(ans1+f[n-cnt])%p,ans2=(ans2+tmp)%p; return; } bool pan=0; inc(i,1,cnt) if(l[dep+1]==l[bo[i]]||r[dep+1]==r[bo[i]]) pan=1; dfs(dep+1,cnt,ssum); if(!pan) bo[cnt+1]=dep+1,dfs(dep+1,cnt+1,ssum+a[l[dep+1]][r[dep+1]]); } int main() { read(n); inc(i,1,n) inc(j,1,n) read(a[i][j]),sumx[i]=(sumx[i]+a[i][j])%p,sumy[j]=(sumy[j]+a[i][j])%p,sum=(a[i][j]+sum)%p; read(k); inc(i,1,k) read(l[i]),read(r[i]),l[i]++,r[i]++; f[0]=1; inc(i,1,300) f[i]=f[i-1]*i%p; dfs(0,0,0); cout<<ans1<<" "<<ans2; } /* 5 2 3 4 5 6 5 4 3 2 1 7 6 5 4 3 5 6 7 8 9 3 4 5 6 7 3 1 2 2 2 3 4 */