2010-1075

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

* 递推公式
{{{
a[ 0 ]     = 0;
a[ 1 ]     = 1 / m * a[ 2 ] + 1;
a[ 2 ]     = ( m - 1 ) / m * a[ 1 ] + 1 / m * a[ 3 ] + 1;
...
a[ i ]     = ( m - 1 ) / m * a[ i - 1 ] + 1 / m * a[ 4 ] + 1; ( 1 <= i < n )
...
a[ n - 1 ] = ( m - 1 ) / m * a[ n - 2 ] + 1 / m * a[ n ] + 1;
a[ n ]     = ( m - 1 ) / m * a[ n - 1 ] + 1 / m * a[ n ] + 1;
}}}
* 解方程方法
    * 迭代法
        顺推( learn from lich's program~ )

            由于已经已经知道了a[ 1 ] = 1 / m * a[ 2 ] + 1;

            那么可以把a[ 1 ] 代入 a[ 2 ] = ( m - 1 ) / m * a[ 1 ] + 1 / m * a[ 3 ] + 1;

            于是知道了a[ 2 ] 与 a[ 3 ] 的关系

            一般的，如果推出了 a[ i ] = k * a[ i + 1 ] + b;

            则: a[ i + 1 ] = k * a[ i ] + b + m / ( m - 1 );

            最后再注意一下n的处理即可..

        逆推( myself )

            由最后一个方程 a[ n ] = ( m - 1 ) / m * a[ n - 1 ] + 1 / m * a[ n ] + 1;

            可得 a[ n ] = a[ n - 1 ] + m / ( m - 1 );

            同样可以把a[ n ] 代入 a[ n - 1 ] = ( m - 1 ) / m * a[ n - 2 ] + 1 / m * a[ n ] + 1;

            于是知道了a[ n - 1 ] 与 a[ n - 2 ] 的关系

            一般的，如果推出了 a[ i + 1 ] = k * a[ i ] + b;

            则： a[ i ] = ( m - 1 ) / ( m - k ) * a[ i - 1 ] + ( m + b ) / ( m - k );

            最后 a[ 1 ] = b[ 1 ];

            再反过来推一遍就得出了n的答案..

    * 矩阵法( learn from icyrhyme )
{{{
        a[1], b[1],    0, ...,   0,    0,    0          
        c[2], a[2], b[2], ...,   0,    0,    0          
           0, c[3], a[3], ...,   0,    0,    0        
        ...     
           0,    0,    0, ...,   0, c[n],  a[n]
}}}
        由于系数矩阵比较特殊，每次可以通过a[i]`, b[i]`消去c[i+1], 然后在O(n)从头开始推一遍即可
* 个人对递推公式的理解
    因为在期望值的计算公式中，E = sum{ p[ i ] * x[ i ] }，对于i - 1 -> i的情况，E` = sum{ 1 / m * p[ i ] * x[ i ] } + 1 = 1 / m * E + 1;

    i + 1 ->　i 的情况亦然，最后由于相对于原来增加了1次操作，所以要统一加上1。

----

by asmn

此题的公式如下，具体推导过程参见[http://10.71.101.90/pia/trac/attachment/wiki/2010-1075/zhouyu.pdf 证明]

[[Image(2010-1075:clip_image002.gif)]]

----
by 猛犸也钻地

补充一下，这道题找规律的做法：

{{{
先写个程序随机模拟了一下，发现
n=1 m=4 ans=1.3333
n=2 m=4 ans=3.1111

想到可能是f(n,m)=g(n,m)/3^n，于是继续算了一下其他的n，发现在m=4时：数列g(n,m)为：
4,28,136,...

有公共系数4，先除掉，得到：
1,7,34,142,547,...

到上面一步好像看不出什么规律，于是尝试作差，得到：
1,6,27,108,405,...

已经很明显了：越往后面，因子3越多，于是除以3^(n-1)，得到：
1,2,3,4,5,...

于是规律就出来了，再验算一下其他的m，就能确定上面的3为(m-1)，公共系数4为m，
再反着带回去把f(n,m)算出来就行了
}}}

代码：
{{{
#include <cstdio>
using namespace std;

double ans[10001][11];

void init(){
    for(int m=3;m<=10;m++){
        ans[1][m]=1.0/(m-1);
        for(int n=2;n<=10000;n++){
            ans[n][m]=n*1.0/(m-1)+ans[n-1][m]/(m-1);
        }
    }
}

int main(){
    init();
    int n,m;
    while(scanf("%d%d",&n,&m)>0){
        for(int i=0;i<m;i++) scanf("%*d");
        printf("%.7f\n",ans[n][m]*m);
    }
}
}}}

----
by frozen

题目描述和数据规模现在已经改掉了，只能用asmn的那种O(1)的方法
  • 递推公式
a[ 0 ]     = 0;
a[ 1 ]     = 1 / m * a[ 2 ] + 1;
a[ 2 ]     = ( m - 1 ) / m * a[ 1 ] + 1 / m * a[ 3 ] + 1;
...
a[ i ]     = ( m - 1 ) / m * a[ i - 1 ] + 1 / m * a[ 4 ] + 1; ( 1 <= i < n )
...
a[ n - 1 ] = ( m - 1 ) / m * a[ n - 2 ] + 1 / m * a[ n ] + 1;
a[ n ]     = ( m - 1 ) / m * a[ n - 1 ] + 1 / m * a[ n ] + 1;
  • 解方程方法

* 迭代法

顺推( learn from lich's program~ )

由于已经已经知道了a[ 1 ] = 1 / m * a[ 2 ] + 1;

那么可以把a[ 1 ] 代入 a[ 2 ] = ( m - 1 ) / m * a[ 1 ] + 1 / m * a[ 3 ] + 1;

于是知道了a[ 2 ] 与 a[ 3 ] 的关系

一般的，如果推出了 a[ i ] = k * a[ i + 1 ] + b;

则: a[ i + 1 ] = k * a[ i ] + b + m / ( m - 1 );

最后再注意一下n的处理即可..

逆推( myself )

由最后一个方程 a[ n ] = ( m - 1 ) / m * a[ n - 1 ] + 1 / m * a[ n ] + 1;

可得 a[ n ] = a[ n - 1 ] + m / ( m - 1 );

同样可以把a[ n ] 代入 a[ n - 1 ] = ( m - 1 ) / m * a[ n - 2 ] + 1 / m * a[ n ] + 1;

于是知道了a[ n - 1 ] 与 a[ n - 2 ] 的关系

一般的，如果推出了 a[ i + 1 ] = k * a[ i ] + b;

则： a[ i ] = ( m - 1 ) / ( m - k ) * a[ i - 1 ] + ( m + b ) / ( m - k );

最后 a[ 1 ] = b[ 1 ];

再反过来推一遍就得出了n的答案..

* 矩阵法( learn from icyrhyme )

     a[1], b[1],    0, ...,   0,    0,    0          
        c[2], a[2], b[2], ...,   0,    0,    0          
           0, c[3], a[3], ...,   0,    0,    0        
        ...     
           0,    0,    0, ...,   0, c[n],  a[n]

由于系数矩阵比较特殊，每次可以通过a[i], b[i]消去c[i+1], 然后在O(n)从头开始推一遍即可

  • 个人对递推公式的理解

因为在期望值的计算公式中，E = sum{ p[ i ] * x[ i ] }，对于i - 1 -> i的情况，E` = sum{ 1 / m * p[ i ] * x[ i ] } + 1 = 1 / m * E + 1;

i + 1 ->　i 的情况亦然，最后由于相对于原来增加了1次操作，所以要统一加上1。

by asmn

此题的公式如下，具体推导过程参见证明

by 猛犸也钻地

补充一下，这道题找规律的做法：

先写个程序随机模拟了一下，发现
n=1 m=4 ans=1.3333
n=2 m=4 ans=3.1111
想到可能是f(n,m)=g(n,m)/3^n，于是继续算了一下其他的n，发现在m=4时：数列g(n,m)为：
4,28,136,...
有公共系数4，先除掉，得到：
1,7,34,142,547,...
到上面一步好像看不出什么规律，于是尝试作差，得到：
1,6,27,108,405,...
已经很明显了：越往后面，因子3越多，于是除以3^(n-1)，得到：
1,2,3,4,5,...
于是规律就出来了，再验算一下其他的m，就能确定上面的3为(m-1)，公共系数4为m，
再反着带回去把f(n,m)算出来就行了

代码：

#include <cstdio>
using namespace std;
double ans[10001][11];
void init(){
    for(int m=3;m<=10;m++){
        ans[1][m]=1.0/(m-1);
        for(int n=2;n<=10000;n++){
            ans[n][m]=n*1.0/(m-1)+ans[n-1][m]/(m-1);
        }
    }
}
int main(){
    init();
    int n,m;
    while(scanf("%d%d",&n,&m)>0){
        for(int i=0;i<m;i++) scanf("%*d");
        printf("%.7f\n",ans[n][m]*m);
    }
}

by frozen

题目描述和数据规模现在已经改掉了，只能用asmn的那种O(1)的方法

附加文件