本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}