bzoj 2510: 弱题概率期望dp+循环矩阵

题目:

Description

有M个球，一开始每个球均有一个初始标号，标号范围为1～N且为整数，标号为i的球有ai个，并保证Σai = M。

每次操作等概率取出一个球（即取出每个球的概率均为1/M），若这个球标号为k（k < N），则将它重新标号为k + 1；若这个球标号为N，则将其重标号为1。（取出球后并不将其丢弃）

现在你需要求出，经过K次这样的操作后，每个标号的球的期望个数。

题解:

神题一个.

首先我们发现没有办法直接对整体进行dp

所以我们先单独考虑一个球.

我们设\(p[i][j]\)表示一个球在i轮后编号向右移动了\(j\)位

简单理解就是\(pos\)变成了\((pos+1)%n\)

那么我们有: \(p[i][j] = p[i-1][j]*\frac{m-1}{m} + p[i-1][j-1]*\frac{1}{m}\)

那么我们有答案\(ans[i] = \sum_{j=0}^{n-1}a[(i-j+n)%n]*p[k][j]\)

所以只要我们计算出\(p[][]\)即可\(O(n^2)\)统计答案

然后关键就是处理\(p[][]\)

但是我们发现\(k\)大的要死,明摆着让我们写矩乘

但是\(n \leq 1000\)矩阵乘法无法直接出解。

但是我们仔细观察一下我们的转移矩阵,发现这个矩阵居然是一个循环矩阵!

所以我们可以直接用\(O(n^2)\)的复杂度完成循环矩阵的乘法。

所以可以将复杂度降到\(O(n^2logk + nlogn)\)

后面的\(nlongn\)是因为可以用FFT计算卷积实现答案的统计.

但是人懒,直接写的n^2的统计,复杂度同阶.

而且貌似n^2的循环展开比FFT还要快.

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

const int maxn = 1024;

int a[maxn];

struct Matrix{

	double s[maxn];

	int n;

	void clear(int n){

		this->n = n;

		memset(s,0,sizeof s);

	}

	friend Matrix operator * (Matrix a,Matrix b){

		Matrix c;c.clear(a.n);

		for(int j=0;j<c.n;++j){

			for(int k=0;k<c.n;++k){

				c.s[j] += a.s[k]*b.s[(j-k+c.n)%c.n];

			}

		}

		return c;

	}

}ori,mul;

double anss[maxn];

int main(){

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

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

	ori.clear(n);

	mul.clear(n);

	ori.s[0] = 1.0;

	mul.s[0] = 1.0*(m-1)/m;

	mul.s[1] = 1.0/m;

	int p = k;

	for(;p;p>>=1,mul=mul*mul) if(p&1) ori = ori*mul;

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

		for(int j=0;j<n;++j){

			anss[i] += a[(i-j+n)%n]*ori.s[j];

		}

	}

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

		printf("%.3lf\n",anss[i]);

	}

	return 0;

}

巴特西

bzoj 2510: 弱题概率期望dp+循环矩阵

题目:

题解:

最新文章

热门文章

巴特西

bzoj 2510: 弱题 概率期望dp+循环矩阵

题目:

题解:

最新文章

热门文章

bzoj 2510: 弱题概率期望dp+循环矩阵