【BZOJ2510】弱题

【样例说明】
第1次操作后，由于标号为2球个数为0，所以必然是一个标号为1的球变为标号为2的球。所以有2个标号为1的球，有1个标号为2的球。
第2次操作后，有1/3的概率标号为2的球变为标号为1的球（此时标号为1的球有3个），有2/3的概率标号为1的球变为标号为2的球（此时标号为1的球有1个），所以标号为1的球的期望个数为1/3*3+2/3*1 = 5/3。同理可求出标号为2的球期望个数为4/3。
【数据规模与约定】
对于10%的数据，N ≤ 5, M ≤ 5, K ≤ 10；
对于20%的数据，N ≤ 20, M ≤ 50, K ≤ 20；
对于30%的数据，N ≤ 100, M ≤ 100, K ≤ 100；
对于40%的数据，M ≤ 1000, K ≤ 1000；
对于100%的数据，N ≤ 1000, M ≤ 100,000,000, K ≤ 2,147,483,647。

题解：一开始too naive，以为同样用一个期望DP的黑科技就能过（k=min(k,5000)）~

发现正解又是矩阵乘法，但是矩乘不是n^3的吗？本题有特殊性质。

我们的DP方程长这样：f[i][j]=f[i的上一个][j-1]/m+f[i][j-1]*(m-1)/m

所以我们的转移矩阵的每一行都是循环相同的，将转移矩阵自乘若干次后，每一行仍然是循环相同的，所以我们的矩阵实际上只需要维护一行，那么转移一次的代价自然就是O(n^2)的。

那么具体实现呢？其实非常简单，直接c[i+j]+=a[i]*b[j]。

#include <cstdio>#include <cstring>#include <iostream>using namespace std;int n,m,k;struct M{	double v[1010];	M (){memset(v,0,sizeof(v));}	double& operator [] (int x)	{return v[x];}	M operator * (M a)	{		M ret;		for(int i=0;i<n;i++)	for(int j=0;j<n;j++)	ret[(i+j)%n]+=v[i]*a[j];		return ret;	}};M ans,x;void pm(int y){	while(y)	{		if(y&1)	ans=ans*x;		x=x*x,y>>=1;	}}int main(){	scanf("%d%d%d",&n,&m,&k);	int i;	for(i=0;i<n;i++)	scanf("%lf",&ans[i]);	x[0]=(double)(m-1)/m,x[1]=(double)1/m;	pm(k);	for(i=0;i<n;i++)	printf("%.3lf\n",ans[i]);	return 0;}