1 条题解
-
0
计 表示序列中 的个数, 表示序列中 的个数。
那么目标的序列就是前面 个 ,后面 个 的序列。
所以如果前 的位置中有 那么这些 出现在哪里都一样。
考虑一个暴力 。
设 表示前 个位置中有 个 ,操作了 次的概率。
容易得到状态转移方程:
$$f_{i,j+1}=f_{i,j}\times (\frac{s_0\times (s_0-1)}{2}+\frac{s_1\times (s_1-1)}{2}+i\times (s_1-i)+i\times (s_0-i)) \\ \\ f_{i-1,j+1}=f_{i,j}\times i\times i \\ \\ f_{i+1,j+1}=f{i,j}\times (s_0-i)\times (s_1-i) $$这样转移的时间复杂度为 ,无法通过此题。
发现 非常小,而 却很大,直接矩阵快速幂即可。
时间复杂度 。
#include<bits/stdc++.h> using namespace std; const int N=105,mod=1e9+7; struct mat{int cnt[N][N];}; int sum,p[N],s[2],siz; mat operator*(mat a,mat b){ mat ans; memset(ans.cnt,0,sizeof(ans.cnt)); for(int i=0;i<=siz;i++) for(int j=0;j<=siz;j++) for(int k=0;k<=siz;k++) ans.cnt[i][j]=(ans.cnt[i][j]+1ll*a.cnt[i][k]*b.cnt[k][j]%mod)%mod; return ans; } int kuai(int a,int b){ int ans=1; for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod; return ans; } mat kuai(mat a,int b){ mat ans; memset(ans.cnt,0,sizeof(ans.cnt)); for(int i=0;i<=siz;i++)ans.cnt[i][i]=1; for(;b;b>>=1,a=a*a)if(b&1)ans=ans*a; return ans; } int n,m; mat a,c; int main(){ std::ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++)cin>>p[i],s[p[i]]++; siz=min(s[0],s[1]); for(int i=1;i<=s[0];i++)sum+=p[i]; a.cnt[0][sum]=1; for(int i=0;i<=siz;i++)c.cnt[i][i]=(1ll*s[0]*(s[0]-1)/2%mod+s[1]*(s[1]-1)/2%mod)%mod; for(int i=0;i<=siz;i++){ if(i>0)c.cnt[i][i-1]=1ll*i*i%mod; (c.cnt[i][i]+=(1ll*i*(s[1]-i)%mod+1ll*(s[0]-i)*i%mod)%mod)%=mod; if(i<siz)c.cnt[i][i+1]=1ll*(s[0]-i)*(s[1]-i)%mod; } int Inv=kuai(1ll*n*(n-1)/2%mod,mod-2); for(int i=0;i<=siz;i++){ if(i>0)c.cnt[i][i-1]=1ll*c.cnt[i][i-1]*Inv%mod; c.cnt[i][i]=1ll*c.cnt[i][i]*Inv%mod; if(i<siz)c.cnt[i][i+1]=1ll*c.cnt[i][i+1]*Inv%mod; } a=a*kuai(c,m); cout<<a.cnt[0][0]; }
- 1
信息
- ID
- 13
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者