bzoj2169 动态规划

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<string>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<iomanip>
 8 using namespace std;
 9 namespace Moxing{
10     const int N=1005;
11     const int mod=10007;
12     //f[i][j]=(f[i-1][j+2]*c[2][j+2]+f[i-1][j-2]*c[2][n-j+2]+f[i-1][j]*(n-j)*j);
13     //f[i][j]-=f[i-2][j]*(c[2][n]-(i-2))
14     int n,m,k,ind[N],f[N][N],sum,inv[N];
15     int c(int x){
16         return (x*(x-1)>>1)%mod;
17     }
18     struct main{
19         main(){
20             scanf("%d%d%d",&n,&m,&k);
21             for(int i=1;i<=m;i++){
22                 int x,y;
23                 scanf("%d%d",&x,&y);
24                 ind[x]++,ind[y]++;
25             }
26             for(int i=1;i<=n;i++) if(ind[i]&1) sum++;
27             f[0][sum]=inv[0]=inv[1]=1;
28             for(int i=1;i<=k;i++){
29                 if(i>1) inv[i]=(mod-1ll*(mod/i)*inv[mod%i]%mod)%mod;
30                 for(int j=0;j<=n;j++){
31                     f[i][j]=f[i-1][j+2]*c(j+2)%mod;
32                     f[i][j]=(f[i][j]+f[i-1][j]*j%mod*(n-j))%mod;
33                     if(j>=2) f[i][j]=(f[i][j]+f[i-1][j-2]*c(n-j+2))%mod;
34                     if(i>=2) f[i][j]=(f[i][j]-f[i-2][j]*(c(n)-i+2)%mod+mod)%mod;
35                     f[i][j]=f[i][j]*inv[i]%mod;
36                 }
37             }
38             cout<<f[k][0];
39             exit(0);
40         }
41     }UniversalLove;
42 } 
43 int main(){
44     Moxing::main(); 
45 }