令f[i][j]表示連i條邊時奇點個數為j的方案數，轉移時討論兩奇點相連、一奇一偶相連、兩偶點相連即可。注意這樣會造成重邊，那么算出恰好有一條重邊的方案數并減掉。由于是有序地考慮每條邊，每次還要除以i。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } #define N 1010 #define P 10007 int n,m,k,degree[N],f[N][N],inv[N],ans,cnt; int C(int n,int m){return (n*(n-1)>>1)%P;} int main() { #ifndef ONLINE_JUDGEfreopen("bzoj2169.in","r",stdin);freopen("bzoj2169.out","w",stdout);const char LL[]="%I64d\n"; #elseconst char LL[]="%lld\n"; #endifn=read(),m=read(),k=read();for (int i=1;i<=m;i++){int x=read(),y=read();degree[x]^=1,degree[y]^=1;}for (int i=1;i<=n;i++) if (degree[i]) cnt++;inv[0]=1;inv[1]=1;for (int i=2;i<=k;i++) inv[i]=P-(P/i)*inv[P%i]%P;f[0][cnt]=1;for (int i=1;i<=k;i++)for (int j=0;j<=n;j++)f[i][j]=(f[i-1][j+2]*C(j+2,2)%P+f[i-1][j]*j%P*(n-j)%P+(j>=2?f[i-1][j-2]*C(n-j+2,2)%P:0)-(i>=2?f[i-2][j]*(C(n,2)-i+2)%P:0)+P)%P*inv[i]%P;cout<<f[k][0];return 0; }

?

轉載于:https://www.cnblogs.com/Gloid/p/9557810.html

總結

以上是生活随笔為你收集整理的BZOJ2169 连边（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。