[uva 11762]Race to 1[概率DP]

时间：2024-09-20 16:06:02

引用自:http://hi.baidu.com/aekdycoin/item/be20a91bb6cc3213e3f986d3,有改动

题意:
已知D, 每次从[1,D] 内的所有素数中选择一个Ni, 如果D = 0(mod Ni), 那么D /= Ni,否则D不变(可以看成是每一轮 D/= GCD(D,Ni) )

思路:
概率DP
令 dp[ i ] 表示 D = i 的时候的期望, 即从i 转移到1 的次数期望. 我们有

p = kcnt[ i ] / cnt[ i ];

kcnt[ i ] 表示i 的素因子种类, cnt[ i ]表示[ 1..i ]内的素数总数, p 表示 D = i 时的D可以在一轮以后减小的概率, 而对于i 的每一种素因子, 取得他们的概率显然都为 1 / cnt[ i ]
假设Ni 是 i 的某个素因子.

[uva 11762]Race to 1[概率DP]

fac[ k ]表示 i 的第 k 个质因子.
后半部分的求和表示从所有的子状态累加上来的期望.
前面则是考虑(1.0 - p)D不变化的情况.

得到kcnt[ ],cnt[ ],fac[ ]就可以得到dp[ ]
优化:
cnt[ ] 可以通过筛选素数以后累加得到
kcnt[ ] 也可以通过筛选素数类似的做法得到
fac[ ]显然也可以预处理得到
而由于处理fac[ i ]的时候需要分解得到 i 的素因子,这里我们继续做一个dpf, dpf[ i ]保存的是 i 的最小素因子, 这样就可以用类似于筛法的过程得到 i 的所有质因子

#include<cstdio>

using namespace std;

const int MAXN = 1000005;

const int MAXP = 100000;

bool ss[MAXN]= {1,1};///筛法求素的数组,前两位(0和1)先标记(没用)...标记代表被筛掉了

/*int p[MAXP],plen = 0;///p[i]表示第i个素数(好像没用)*/

int cnt[MAXN];///i以内素数个数

int kcnt[MAXN];///i的素因子种类数

int dpf[MAXN];///i的最小质因子

double dp[MAXN];///从i转移到1的期望

int fac[305],flen;

///求i的...

void process(int n)

{

    int i;

    int on = n;

    flen = 0;

    /*

    while(n!=1&&dpf[n]!=n)///没有到分解完毕并且下一步也不会分解完毕

    {

        if(flen == 0 ||dpf[n]!=fac[flen -1])///如果相同,则不记录,只继续除.

            fac[flen++] =dpf[n];///记录n的新的一种素因子(一个一个分解)

        n/=dpf[n];///除去这个素因子

    }

    if(dpf[n] == n)///如果即将分解完毕

        if(flen == 0 ||n!=fac[flen -1])///如果需要记录,则记录

            fac[flen++] = n;

    */

    while(n!=1)///没有分解完毕

    {

        if(flen == 0 ||dpf[n]!=fac[flen -1])///如果相同,则不记录,只继续除.

            fac[flen++] =dpf[n];///记录n的新的一种素因子(一个一个分解)

        n/=dpf[n];///除去这个素因子

    }

    n = on;

    for(i=0; i<flen; ++i)dp[n] += (dp[n/fac[i]]+1.0) / cnt[n];///sigma

}

void mklist()

{

    int i,j;

    dpf[1] = 0;

    for(i=2; i<MAXN; ++i)

        if(!ss[i])

            for(j=i; j<MAXN; j+=i)

            {

                if(!ss[j])

                    dpf[j] =i;///dpf[j]记录着j的最小素因子

                if(j!=i)

                    ss[j] = 1;///如果不是素数本身,就筛掉

            }

    cnt[0] = cnt[1] = 0;

    for(i=2; i<MAXN; ++i)///数组筛好了之后

        if(!ss[i])

            /*p[plen++]=i,*/

            cnt[i] = cnt[i-1]+1;

        else

            cnt[i] = cnt[i-1];

    for(i=2; i<MAXN; ++i)

        if(kcnt[i] == 0)///i为素数

            for(j=i; j<MAXN; j+=i)

                ++kcnt[j];///像筛法一样求每个数的素因子种类数

    dp[1] = 0.0;

    for(i=2; i<MAXN; ++i)

    {

        double p = 1.0*kcnt[i]/cnt[i];///总的转移的概率

        dp[i] = (1.0-p);///停留在原地的概率(公式整理得到)

        process(i);///把分解质因子和dp过程合在了一起

        dp[i] /= p;

    }

}

int main()

{

    mklist();

    int t;

    int idx = 0,n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        ++idx;

        printf("Case %d: ",idx);

        printf("%.10lf\n",dp[n]);

    }

    return 0;

}

uva目前上不去...改日自己再交

相关文章