题目大意
题目分析
bzoj2201
设$f(i,j)$表示前$i$个珠子，第$i$个珠子是否与第一个相同的期望值，$p(i)$为$i$个珠子颜色相同的概率。
这样可以写出一个简单的$n^2$的转移。
答案先统计进入环上全是一种颜色的方案数，再累加$i\cdot i\cdot f(n-i,0)\cdot p(i)$。
意思是枚举第一个珠子所在段长度$i$，故第一个珠子有$i$个地方可放，其余的调用DP数组即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=205;
int n,m;
double p[maxn],f[maxn][2];
int main() {
n=Get_Int();
m=Get_Int();
p[1]=1;
for(int i=2; i<=n; i++)p[i]=p[i-1]/m;
f[0][1]=1;
for(int i=0; i<=n; i++)
for(int j=i+1; j<=n; j++) {
f[j][0]+=(j-i)*p[j-i]*(f[i][0]*(m-2)/m+f[i][1]*(m-1)/m);
f[j][1]+=(j-i)*p[j-i]*f[i][0]/m;
}
double ans=p[n]*n;
for(int i=1; i<n; i++)ans+=i*i*p[i]*f[n-i][0];
printf("%0.5lf\n",ans);
return 0;
}
bzoj2207
上面的DP中，DP的系数都是固定的，因此可以做个$f(,0/1)$前缀和，就不需要枚举转移自的地方了。
注意细节很多。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=1000005;
int n,m;
double p[maxn],f[2],sum0,sum1,last0,last1;
int main() {
n=Get_Int();
m=Get_Int();
p[1]=1;
for(int i=2; i<=n; i++)p[i]=p[i-1]/m;
for(int i=2; i<=n; i++)p[i]*=i;
for(int i=1; i<n; i++) {
f[0]=p[i]*i*(m-1)/m+sum0*(m-2)/m+sum1*(m-1)/m;
f[1]=sum0/m;
sum0=(sum0+last0)/m+f[0];
sum1=(sum1+last1)/m+f[1];
last0=last0/m+f[0];
last1=last1/m+f[1];
}
printf("%0.5lf\n",sum0+p[n]);
return 0;
}
