E. Number of Components
- 当时思博了。。一直在想对于\([1,r]\)的联通块和\([1,l-1]\)的联通块推到\([l,r]\)的联通块...我真的是傻了。。这题明明很水啊..换做以前肯定是可以做出来的!(flag*1)
由于是一条链,那么我们考虑就算一个联通块中的最小节点为\(i\)对答案所产生的贡献...不就是满足\(i\)而不满足\(i-1\)的\([l,r]\)区间有多少个吗!(我真的好菜啊!这题明明很水!
F. Sonya and Informatics
-
神仙吧这题!
一直以为自己是懂矩阵优化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\)交换了 方案数为\(i*(zero-i)\)
- 后面的数\(0\)与\(1\)交换了 方案数为\((zero-i)*( one-(zero-i) )\)
转移即为
\[dp[i+1][j]=dp[i][j]*(one*(one-1)/2+zero*(zero-1)/2+i*(zero-i)+(zero-i)*(one-(zero-i)))\]
但是这个复杂度是\(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;
}