2510: 弱题
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 124 Solved: 61
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
3 0
Sample Output
1.333
HINT
【样例说明】
第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。
这道题有两种解法,一中是预处理每一个位置经过k次到达另外位置的概率,七中运用到了类似于倍增的方法,求经过2^i次转移后的概率数组,然后在计算k次。
另一种解法在网上已经有提到,观察转移矩阵是一个“循环矩阵”,即每一行都是上一行通过右移得到,循环矩阵A、B满足A*B=C,那么C也是循环矩阵,则这样的矩阵做乘法只用O(n^2),原因是一个矩阵只需要O(n)的空间就可以储存,而答案矩阵每一个元素都能用乘数矩阵通过O(n^2)错位相乘得出,具体细节自行脑补。总之我觉得非常神奇。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAXN 1099
typedef double real;
int n,m,tt;
real mat[MAXN];
real res[MAXN];
real tmp[MAXN];
real ans[MAXN];
int tot[MAXN];
void mul(real res[],real m1[],real m2[])
{
memset(res,,sizeof(real)*MAXN);
for (int i=;i<m;i++)
for (int j=;j<m;j++)
res[(i+j+m)%m]+=m1[i]*m2[j];
} int main()
{
//freopen("input.txt","r",stdin);
scanf("%d%d%d",&m,&n,&tt);
for (int i=;i<m;i++)
scanf("%d",tot+i);
mat[]=1.0/n;
mat[]=(n-1.0)/n;
res[]=;
while (tt)
{
if (tt&)
{
mul(tmp,res,mat);
memcpy(res,tmp,sizeof(tmp));
}
mul(tmp,mat,mat);
memcpy(mat,tmp,sizeof(tmp));
tt>>=;
}
for (int i=;i<m;i++)
{
for (int j=;j<m;j++)
{
ans[i]+=tot[j]*res[(i-j+m)%m];
}
printf("%.3lf\n",ans[i]);
}
return ;
}