题目:
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;
}