[ABC300E] Dice Product 3-概率期望DP

wflengxuenong · 2024-01-05 16:29:47 · 个人记录

• 题目大意 给定一个数1，不断乘上骰子的点数，问恰好为n的概率是多少？

• 题目分析

1出现与否没有影响，因此2 3 4 5 6共5种可能，每个数出现的概率为1/5. 也可以通过等比数列推导出。 或者通过递推得到 f(x）=1/6(f(x)+f(x/2)+f(x/3)+f(x/4)+f(x/5)+f(x/6)） f(x)=1/5(f(x/2)+f(x/3)+f(x/4)+f(x/5)+f(x/6))

方法一:利用排列组合 唯一分解定理后，处理2,3，是合起来得到4,6，还是分着得到. 例如样例：300

$2*2*3*5*5   5!/(2!2!)$  

$4*3*5*5   4!/2!$

$2*6*5*5 4!/2!$

方法二： 用前面的递推公式，n太大，记忆化搜索，利用map完成记忆化

方法一代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int MAXV = 200000;
int inv[MAXV + 10], jc[MAXV + 10], invjc[MAXV + 10];
int ksm(int a, int b, int res = 1) {
    for (; b; a = a * a % mod, b >>= 1)
        if (b & 1) res = res * a % mod;
    return res;
}
void init() {
    jc[0] = 1;
    for (int i = 1; i <= MAXV; i++)
        jc[i] = jc[i - 1] * i % mod;
    invjc[MAXV] = ksm(jc[MAXV], mod - 2);
    for (int i = MAXV; i > 0; i--)
        invjc[i - 1] = invjc[i] * i % mod;
    for (int i = 1; i <= MAXV; i++)
        inv[i] = jc[i - 1] * invjc[i] % mod;
}
int C(int x, int y) {
    return jc[x] * invjc[y] % mod * invjc[x - y] % mod;
}
signed main() {
    init();
    int n, cnt2 = 0, cnt3 = 0, cnt5 = 0;
    scanf("%lld", &n);
    while (n % 2 == 0) cnt2++, n /= 2;
    while (n % 3 == 0) cnt3++, n /= 3;
    while (n % 5 == 0) cnt5++, n /= 5;
    if (n > 1) {
        puts("0");
        return 0;
    }
    int ans = 0,res;
    for (int i = 0; i <= cnt2; i++) {

        for (int j = 0; j <= cnt3; j++) {
            int cnt6 = cnt3 - j;
            if (cnt2 - i - cnt6 < 0 || (cnt2 - i - cnt6) % 2)
                continue;
            int cnt4 = (cnt2 - i - cnt6) / 2;
            int all = i + j + cnt4 + cnt5 + cnt6;
            int sum = ksm(5, all);
            res = C(all, i);
            res = res * C(all - i, j) % mod;
            res = res * C(all - i - j, cnt4) % mod;
            res = res * C(all - i - j - cnt4, cnt5) % mod;
            res = res * C(all - i - j - cnt4 - cnt5, cnt6) % mod;
            (ans += res * ksm(sum, mod - 2) % mod) %= mod;
        }
       //printf("%lld\n", res);
        }
    printf("%lld\n", ans);

    return 0;
}

方法二：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int MAXV = 200000;
int n,inv5;
int ksm(int a, int b, int res = 1) {
    for (; b; a = a * a % mod, b >>= 1)
        if (b & 1) res = res * a % mod;
    return res;
}
map<int,int> dp;
map<int,bool> v;
int dfs(int x)
{
    if(x<1) return 0;
    if(x==1) return 1;
    if(v[x]==true) return dp[x];
    v[x] = true;

    for(int i=2;i<=6;i++) {
     if(x%i==0)  dp[x]=(dp[x]+dfs(x/i))%mod ;
    }
    dp[x] = (dp[x]*inv5)%mod;
    return dp[x];
}
signed main() {
    inv5=ksm(5,mod-2);
    scanf("%lld", &n);
    printf("%lld\n",dfs(n));
    return 0;
}