edward_mj

[SGU385 Highlander]【数学期望】【组合数学】【动态规划】

【题意】

输入n，求在所有错位排列中，在最长循环节上点的数目(如果有多个最长循环节，那么这些上面的点都要算)的期望值。

每个错排都是等概率的。

【算法】

论文上的题…写出来加深印象+方便回看。

因为是排列，而且是错排，所以可以看成无自环的多个独立环拼成的图。

F[i][j][k]表示选了i个数里面最长循环节是j，有k个最长循环节时的方案数。

令G[i][j]=Sum(F[i][0..j][k])

初始化F[0][0][0]=1。

F[i][j][k]=

{

G[i-j][j-1]*P(n-i+j,j)/j k=1 就是在剩下的n-i+j个数里取j个，得到一个长度为j的排列,但是由于是环,可以循环一圈当同样的，所以/j

F[i-j][j][k-1]*P(n-i+j,j)/j/k k>1 前面和上面一样.后面的/k是把这k个等长的环的顺序上的重复干掉。

}

最后答案就是Sum( F[n][j][k]*j*k ) / d

d是错排数目。

【CODE】

https://ideone.com/lIAQX

【转】zoj 1007

很靠前的一道题，到今天才做，主要是突然发现他是一道很纯的数学题，，，拿到题后看了下，并没有怎么弄第三个式子，没管，自己化。要想减少循环的次数，必须把每次计算的级数提高，y(x) – y(1) 这个是重点，推式子就是从这里开始的，推到后来就自然地要用到第三个式子了，那些符号不知道怎么打，不过发现在网上有人已经写了，就是这样的方法，摘录如下：

假设n是要达到精度要求的要计算到的数:

到这里就差不多了，e*中我觉得只要考虑后面部分就可以了，在大于n时是小于1/(3*n^3)的，在n达到4次方的数量级时，误差就小于10^-12了，所以计算的次数就在10000以内了，开始的时候为了保险，开了100000，6秒多过了，后来一步步往下降，到8000也可以，0.5秒多，5000就不行，中间就没试了，没意思的，反正是达不到一大片人的0.00s，0.01s了，郁闷～～～～～

code：

#include "stdio.h"
int main()
{
double sum,x,k;
int i;
x=0.000;
for (i=0;i<=2000;i++)
{
   sum=0.0;
   for (k=1;k<8000;k++)
    sum+=1/(k*(k+1)*(k+2)*(k+x));
   sum=((2-x)*sum+0.25)*(1-x)+1;
   printf("%5.3f %16.12fn",x,sum);
   x+=0.001;
}
return 0;
}