[LightOJ1038] Race to 1 Again

2018/07/21 13:01
阅读数 25

传送门:>出错啦<

题意:给你一个整数n,每一次可以随机选择一个n的因子x(包括1和它自己),让n除以x——不停重复此过程,直到n==1. 问n被除到1的期望次数。

解题思路:

  今天刚学的期望Dp,这道题就算入门啦,顺带总结一下期望Dp的做题方法。

  一般的,我们可以设$f[i]$表示从状态i到目标状态的期望次数。因此我们可以先确定本题的目标状态——n变为1. 因此在本题中,我们可以设$f[i]$表示$n==i$时到$n==1$的期望次数。由于目标状态本身到目标状态是根本不用变的,因此先确定$f[1] = 1$

  于是由于最小的已经确定了,我们可以从1开始推:由小的来确定大的。因此我们可以枚举i,再枚举i的所有因子。设i的因子为$a_1, a_2, ..., a_m$,则有:$$f[i] = \frac{f[a_1] + f[a_2] + ... + f[a_m]}{m} + 1$$

  即f[i]可以通过除一次来得到所有的这些因子(是得到这些因子,并不是除掉,想一想为什么),因此$f[i]$变成1的期望就是它变成的所有这些因子的期望的平均值,再加上本次的这个1.

  然而很快会发现,$a_m = i$,$f[i]$总不可能用自己来转移自己吧……因此我们需要对方程进行变形

  一般处理期望这些问题的用得都是实数,所以可以当代数式来做:

  两边同时乘以$m$,$$f[i] * m = f[a_1] + f[a_2] + ... + f[i] + m$$ $$f[i] * (m - 1) = f[a_1] + f[a_2] + ... + f[a_{m-1}] + m$$ $$f[i] = \frac{f[a_1] + f[a_2] + ... + f[a_{m-1}] + m}{m - 1}$$

Code

  要注意的是,直接$O(n^2)$枚举会超时,所以我们可以$O(n\sqrt{n})$,再$O(\sqrt{n})$的时间内搞出所有因子——特判一下完全平方数即可

 

/*By QiXingzhi*/
#include <cstdio>
#include <cmath>
#include <queue>
#define  r  read()
#define  Max(a,b)  (((a)>(b)) ? (a) : (b))
#define  Min(a,b)  (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int INF = 1061109567;
inline int read(){
    int x = 0; int w = 1; register int c = getchar();
    while(c ^ '-' && (c < '0' || c > '9')) c = getchar();
    if(c == '-') w = -1, c = getchar();
    while(c >= '0' && c <= '9') x = (x << 3) +(x << 1) + c - '0', c = getchar();
    return x * w;
}
int T,Case,N;
double f[100010];
inline void Solve(int N){
    f[1] = 0.0;
    double m = 0.0, K = 0.0;
    double flg = -1.0;
    for(int i = 2; i <= N; ++i){
        K = 0.0;
        m = 0.0;
        flg = -1.0;
        for(int j = 1; j <= floor(sqrt(i)); ++j){
            if(i % j == 0){
                m += 1.0;
                K += f[j];
                if(i % (i/j) == 0){
                    m += 1.0;
                    K += f[i/j];
                    if(i/j == j){
                        flg = f[j];
                    }
                }
            }
        }
        if(flg != -1.0){
            K -= flg;
            m -= 1.0;
        }
        f[i] = (double)(K + m) / (double)(m - 1);
    } 
}
int main(){
    Solve(100000);
    T = r;
    while(T--){
        N = r;
        ++Case;
        printf("Case %d: %.8lf\n",Case, f[N]);
    }
    return 0;
}

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部