bzoj4204: 取球游戏

好神啊..

首先递推随便yy一下就行了

然后发现可以用矩阵优化，不过显然是n^3logk的，不资磁

于是就有了性质，这个转移矩阵显然是一个循环矩阵（并不知道）

循环矩阵乘循环矩阵还是循环矩阵

然后就可以O(n)记录矩阵，O(n^2)完成乘法

然后就资磁啦

复杂度O(n^2logn)

详见代码

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#define N 1003

using namespace std;

inline int read(){

	int ret=0;char ch=getchar();

	while (ch<'0'||ch>'9') ch=getchar();

	while ('0'<=ch&&ch<='9'){

		ret=ret*10-48+ch;

		ch=getchar();

	}

	return ret;

}

struct matrix{

	int size;

	double a[N];

} A;

#define val(z,u,v) z.a[(v-u+z.size)%z.size+1]

inline matrix operator *(const matrix &x,const matrix &y){

	matrix ret;

	ret.size=x.size;

	for (int i=1;i<=ret.size;++i){

		ret.a[i]=0;

		for (int j=1;j<=ret.size;++j)

			ret.a[i]+=x.a[j]*val(y,j,i);

	}

	return ret;

}

inline matrix pow_mat(matrix x,int y){

	matrix ret;

	ret.size=x.size;

	memset(ret.a,0,sizeof(ret.a));

	ret.a[1]=1;

	while (y){

		if (y&1) ret=ret*x;

		x=x*x;

		y=y>>1;

	}

	return ret;

}

int a[N];

int main(){

	int n=read(),m=read(),k=read();

	for (int i=1;i<=n;++i) a[i]=read();

	if (n==1){printf("%.3f\n",(double)m);return 0;}

	A.size=n;

	memset(A.a,0,sizeof(A.a));

	A.a[1]=(double)(m-1)/(double)m;

	A.a[2]=1.0/(double)m;

	A=pow_mat(A,k);

	for (int i=1;i<=n;++i){

		double now=0;

		for (int j=1;j<=n;++j)

			now+=(double)a[j]*val(A,j,i);

		printf("%.3f\n",now);

	}

	return 0;

}

双倍经验万岁

bzoj2510