2019.3.26考试

60pts：

只需要考虑删一个固定两个自由和两个固定一个自由的情况，转成一般图最大匹配

好像数据比较水可以用奇怪的方法搞

正解：

咕

做呢

推的式子和正解差了一些东西 gg

 1 #include<cstdio>
 2 const int N=1005,M=1e6+60,mod=1e9+7;
 3 int T,n,m,k,fac[M],inv[M],stl[N][N];
 4 int Qpow(int x,int k)
 5 {
 6     if(k<=1) return k?x:1;
 7     int tmp=Qpow(x,k>>1);
 8     return 1ll*tmp*tmp%mod*((k&1)?x:1)%mod;
 9 }
10 void Pre()
11 {
12     stl[0][0]=1;
13     int lim1=1000,lim2=1000000;
14     for(int i=1;i<=lim1;i++)
15         for(int j=1;j<=lim1;j++)
16             stl[i][j]=(stl[i-1][j-1]+1ll*stl[i-1][j]*j%mod)%mod;
17     fac[0]=inv[0]=1;
18     for(int i=1;i<=lim2;i++) fac[i]=1ll*fac[i-1]*i%mod;
19     inv[lim2]=Qpow(fac[lim2],mod-2);
20     for(int i=lim2-1;i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
21 }
22 int C(int a,int b)
23 {
24     return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;
25 }
26 int Sq(int x)
27 {
28     return 1ll*x*x%mod;
29 }
30 int main()
31 {
32     scanf("%d",&T),Pre();
33     while(T--)
34     {
35         scanf("%d%d%d",&n,&m,&k);
36         if(m==1) printf("%d
",Qpow(k,n));
37         else if(m==2) 
38         {
39             int ans=0;
40             for(int i=1;i<=k;i++)
41             {
42                 if(i>n) break;
43                 (ans+=Sq(1ll*C(k,i)*stl[n][i]%mod*fac[i]%mod))%=mod;
44             }
45             printf("%d
",ans);
46         }
47         else
48         {
49             int ans=0;
50             for(int i=1;i<=n;i++)
51                 for(int j=1;j<=i;j++)
52                 {
53                     int ch=1ll*C(k,i)*C(k-i,i-j)%mod*C(i,j)%mod;
54                     int md=1ll*Sq(1ll*stl[n][i]*fac[i]%mod)*Qpow(j,n*(m-2))%mod;
55                     (ans+=1ll*ch*md%mod)%=mod; 
56                 }
57             printf("%d
",ans);
58         }
59     }
60     return 0;
61 }

View Code

orz shj

这种和顺序无关的见了好几次了，找个小本本记下来