题意 : 一开始给你一个数D然后随机从它的因子中找出一个x,进行D = D / x操作, 这样算一步,直到D=1结束,问你P(D)的期望是几步。
思路 : 建边之后就是典型的概率DP题,状态转移方程式 : P(D) = (∑(P(D的非1和本身因子)+1) + 2) / (因子数+1) ;
#include <cstdio> #include <cstring> const int maxn = 100005; const double eps = 1e-7; struct Edge{ int to, next; }edge[maxn*20]; double dp[maxn]; int E, head[maxn]; void add_edge(int u, int to){ edge[E].to = to; edge[E].next = head[u]; head[u] = E++; } void init(){ E = 0; memset(head, -1, sizeof(head)); for (int i = 0; i < maxn; i++)dp[i] = 0.0; for (int x = 100000; x >= 2; x--){ for (int i = 2; i * i <= x; i++)if (x % i == 0){ add_edge(x, i); if (x / i != i)add_edge(x, x/i); } } } double dfs(int u){ if (dp[u] >= eps)return dp[u]; if (u == 1)return 0.0; double sum = 2; int cnt = 2; for (int i = head[u]; i != -1; i = edge[i].next){ cnt++; sum += dfs(edge[i].to) + 1; } return dp[u] = sum / (cnt-1); } int main(){ int T, n; init(); scanf("%d", &T); for (int cas = 1; cas <= T; cas++){ scanf("%d", &n); printf("Case %d: %f\n", cas, dfs(n)); } return 0; }