Description
题目链接: https://codeforces.com/contest/1151/problem/F
题意是说给一个长度为 $n$ 且只由 01 组成的序列（例如 100110），问 $k$ 次操作后有多大概率将原序列变为 000…111 这样的新序列，每次操作是随机选两个位置并对位置上的数进行交换.
题目限制:
$2 \le n \le 100, 1 \le k \le 10^9$
Solution
可以考虑一个动态规划.
我们记 $cur$ 为序列中 $0$ 的个数，并定义 $dp[i][j]$ 为 $i$ 次操作后前 $cur$ 个位置有 $j$ 个 $0$ 的方案数，容易想到，若想得到题意所需的新序列，则需要在前 $cur$ 个位置中有 $cur$ 个 $0$. 我们所要求的就是 $\frac{dp[k][cur]}{\sum_{i=0}^{cur}dp[k][i]}$.
考虑状态的转移，$dp[i][j]$ 可以通过一次操作由 $dp[i-1][j-1]$、$dp[i-1][j]$、$dp[i-1][j+1]$转移过来.
根据我们所定义的状态，我们可以知道对于 $dp[i][j]$ ，前 $cur$ 个位置中有多少 $0$ 和 $1$，也知道后 $n-cur$ 个位置有多少 $0$ 和 $1$.
以 $dp[i-1][j-1]$ 为例，它前 $cur$ 个位置中有 $j-1$ 个 $0$ 和 $cur-j+1$ 个 $1$，后 $n-cur$ 个位置中有 $cur-j+1$ 个 $0$ 和 $n-2×cur+j-1$ 个 $1$，通过交换前 $cur$ 个位置中的某个 $1$ 和后 $n-cur$ 个位置中的某个 $0$ 即可完成 $dp[i-1][j-1]$ 到 $dp[i][j]$ 的转移，即 $dp[i][j]+=dp[i-1][j-1]×(cur-j+1)×(cur-j+1)$.
其他情况的转移方程同理可得，再套一个矩阵快速幂就可以在 $O(n^3logk)$ 的时间里得到答案了.
Tips: 注意初始化和一些边界的情况.
AC code
Time: 686ms
Memory: 700KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;
#define mem(a,i) memset(a,i,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&-x)
#define sqr(x) ((x)*(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
const ll mod=1e9+7;
const int maxn=105;
int n;
ll k;
int p[maxn];
struct matrix {
ll a[maxn][maxn];
void clear() {
mem(a,0);
}
};
matrix mul(matrix x,matrix y) {
matrix z;
z.clear();
rep(i,0,maxn-1) {
rep(j,0,maxn-1) {
rep(t,0,maxn-1) {
z.a[i][j]=(x.a[i][t]*y.a[t][j]%mod+z.a[i][j])%mod;
}
}
}
return z;
}
int solve(int x) {
if(x==0) return 0;
return x*(x-1)/2;
}
ll qpow(ll a,ll n) {
ll res=1;
ll p=a%mod;
while(n) {
if(n&1) res=res*p%mod;
p=p*p%mod;
n>>=1;
}
return res;
}
int main() {
scanf("%d%lld",&n,&k);
int cur=0;
rep(i,1,n) {
scanf("%d",&p[i]);
if(!p[i]) cur++;
}
int x=0;
rep(i,1,cur) {
if(!p[i]) x++;
}
matrix ans;
ans.clear();
ans.a[x][0]=1;
matrix tr;
tr.clear();
rep(j,0,cur) {
if(cur-j>=0&&n-2*cur+j>=0) {
tr.a[j][j]=solve(cur)+solve(n-cur)+j*(cur-j)+(cur-j)*(n-2*cur+j);
}
if(j-1>=0&&n-2*cur+j-1>=0) tr.a[j][j-1]=(cur-j+1)*(cur-j+1);
if(j+1<=cur&&n-2*cur+j+1>=0) tr.a[j][j+1]=(j+1)*(n-2*cur+j+1);
}
while(k) {
if(k&1) ans=mul(tr,ans);
tr=mul(tr,tr);
k>>=1;
}
ll res=ans.a[cur][0];
ll q=0;
rep(i,0,cur) q=(q+ans.a[i][0])%mod;
res=res*qpow(q,mod-2)%mod;
printf("%lld\n",res);
return 0;
}