传送链接
神仙吧这题!一直以为自己是懂矩阵优化DP的。。现在发现自己知道的东西真的只是一点皮毛而已呢!woc。。瞬间不想继续颓废下去了
一看这个数据范围\(n \leq 100,k \leq 10^9\)
矩阵乘法!
我们先考虑一个肥肠暴力的\(dp\)再考虑矩阵乘法优化 因为如果你要搞出一个非下降的那么一定是\(0\)在前面而\(1\)在后面的 设一共有\(zero\)个\(0\),\(one\)个\(1\) 那么我们就可以设\(dp[i][j]\)表示第\(i\)次操作使得前面\(zero\)个数中有\(j\)个\(0\)的方案数 最后所求即为\[\frac{dp[k][zero]}{(n*(n-1)/2)^{k}}\] 转移应该也还蛮好懂的趴!\(dp[i][j]\) 可以转移到\(dp[i+1][j-1],dp[i+1][[j],dp[i+1][j+1]\) 那菜鸡博主就举个例子
\(dp[i][j] \Rightarrow dp[i+1][j]\) 一步操作,前面\(zero\)里面\(0\)的个数并没有改变,那么一定是下面的请况
\(1\)与\(1\)交换了 方案数为\(one*(one-1)/2\)\(0\)与\(0\)交换了 方案数为\(zero*(zero-1)/2\)前面\(zero\)个数中\(0\)与\(1\)交换了 方案数为\(j*(zero-j)\)后面的数\(0\)与\(1\)交换了 方案数为\((zero-j)*( one-(zero-j) )\)转移即为
\[dp[i+1][j]=dp[i][j]*(one*(one-1)/2+zero*(zero-1)/2+j*(zero-j)+(zero-j)*(one-(zero-j)))\]
但是这个复杂度是\(O(nk)\)哒 显然过不了嘛
矩阵优化也很容易转换(好吧。对于我这只菜鸡来说并不QwQ.
事实上,这题是将转移的系数进行了优化(不知道这么说对不对。。)
好像准确地来说应该是概率
即对于一个矩阵\(A[i][j]\) 表示从前\(zero\)个数中\(0\)的个数由\(i\)变成\(j\)的方案数
我们可以直接预处理出\(A[i][i],A[i][i+1],A[i][i-1]\) 这是转移一次的
转移\(k\)次 即将\(A\)这个矩阵乘个\(k\)遍就行了 矩阵快速幂用一下即可.
贴个代码趴!
#include<bits/stdc++.h> #define fr(i,x,y) for(int i=x;i<=y;++i) #define rf(i,x,y) for(int i=x;i>=y;--i) #define ll long long using namespace std; const int N=110,mod=1e9+7; struct data{ ll a[N][N]; }qx; ll qwq,inv; int n,k,b[N]; void Add(ll &x,ll y){ x=(x+y)%mod; } void Mul(ll &x,ll y){ x=(x*y)%mod; } ll add(ll x,ll y){ return (x+y)%mod; } ll mul(ll x,ll y){ return x*y%mod; } ll q_pow(ll x,int y){ ll ans=1; for(;y;y>>=1){ if(y&1) Mul(ans,x); Mul(x,x); } return ans; } data cal(data A,data B){ data C; fr(i,0,n) fr(j,0,n){ C.a[i][j]=0; fr(k,0,n) Add(C.a[i][j],mul(A.a[i][k],B.a[k][j])); } return C; } data ksm(data A,int y){ data B; fr(i,0,n) fr(j,0,n) B.a[i][j]=(i==j); for(;y;y>>=1){ if(y&1) B=cal(A,B); A=cal(A,A); } return B; } ll cal(ll x){ return mul(mul(x,x-1),qwq); } int main(){ scanf("%d%d",&n,&k); qwq=q_pow(2,mod-2),inv=q_pow(q_pow(cal(n),mod-2),k); int zero=0,one=0; fr(i,1,n){ scanf("%d",&b[i]); if(b[i]) one++; else zero++; } int nw=0; fr(i,1,zero) if(!b[i]) nw++; data gg; fr(i,0,zero){ if(n-zero-zero+i<0) continue; gg.a[i][i]=add(add(add(cal(zero),cal(one)),mul(i,zero-i)),mul(zero-i,one-zero+i)); gg.a[i][i+1]=mul(zero-i,zero-i); if(i) gg.a[i][i-1]=mul(i,one-zero+i); } // fr(i,0,zero) fr(j,0,zero){ // printf("a[%d][%d]=%lld\n",i,j,gg.a[i][j]); // } gg=ksm(gg,k); ll ans=mul(gg.a[nw][zero],inv); cout<<ans<<endl; return 0; }转载于:https://www.cnblogs.com/lowbigpei/p/10735174.html