【期望DP+循环矩阵】BZOJ2510 弱题

题面在这里

​

\(f_{i,j}\)表示\(i\)次操作后，编号为\(j\)的球的个数期望

则\(f_{i,j}=\frac 1 m f_{i-1,j-1}+\frac{m-1} m f_{i-1,j}\)

发现这是一个循环矩阵，那么只需要维护第一行即可，时间复杂度\(O(n^2\log K)\)

​

示例程序：

#include<cstdio>
#include<cstring>
#define cl(x,y) memset(x,y,sizeof(x))

const int maxn=1005;
int n,m,K;
struct data{
	double s[maxn];
	data () {cl(s,0);}
}f,t;
data operator*(const data&a,const data&b){
	data c;
	for (int i=0;i<n;i++)
	 for (int j=0;j<n;j++)
	  c.s[(i+j)%n]+=a.s[i]*b.s[j];
	return c;
}
data Pow(data a,int b){
	data w=a,res;res.s[0]=1;
	while (b){
		if (b&1) res=res*w;
		w=w*w;
		b>>=1;
	}
	return res;
}
int main(){
	scanf("%d%d%d",&n,&m,&K);
	for (int i=0;i<n;i++) scanf("%lf",&f.s[i]);
	t.s[0]=(m-1.0)/m; t.s[1]=1.0/m;
	f=f*Pow(t,K);
	for (int i=0;i<n;i++) printf("%.3lf\n",f.s[i]);
	return 0;
}