题目描述

难度分:$1354$

输入$n(1 \leq n \leq 10^{18})$。

你有一个整数$x$，初始值为$1$。

你有一个六面的骰子，可以等概率地掷出$1$~$6$。

不断重复如下操作，直到$x \geq n$为止：

• 掷骰子，把$x$乘上骰子显示的数字。

问：当你停止操作时，$x$恰好等于$n$的概率是多少？

设概率为$\frac{a}{b}$，输出分数取模的结果，其中$mod=998244353$。

输入样例$1$

6

输出样例$1$

239578645

输入样例$2$

7

输出样例$2$

0

输入样例$3$

300

输出样例$3$

183676961

输入样例$4$

979552051200000000

输出样例$4$

812376310

算法

概率DP

一眼就是概率DP，比较典。

状态定义

$dp[x]$表示从$x$扔到$n$的概率，显然答案就是$dp[1]$。

状态转移

每次扔骰子可以扔出$6$个点数，状态转移方程为

$dp[x]=\frac{\Sigma_{p=1}^{6}dp[p \times x]}{6}$

此时发现如果一直掷出点数$1$，就会无限依赖，因此把状态转移方程变形为

$dp[x]=\frac{\Sigma_{p=2}^{6}dp[p \times x]}{5}$

这样就可以做了，最后边界条件为：当$x \gt 0$时，$dp[x]=0$，当$x=n$时，$dp[x]=1$。

复杂度分析

时间复杂度

每一轮都有$5$个分支，可以发现，只要没有$1$这个分支，复杂度就是$logn$级别的（因为$x \times p^y=n$，初始情况下$x=1$，那么$y$就是$log_pn$），只是底数为$[2,6]$。因此，整体的时间复杂度为$O(logn)$。

空间复杂度

采用记忆化搜索来实现DP，递归深度为$logn$级别，状态数量也是这个级别。因此，额外空间复杂度也为$O(logn)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
typedef long long LL;
const int MOD = 998244353, inv5 = 598946612;
LL n;

int dfs(LL x, unordered_map<LL, int>& dp) {
    if(x > n) return 0;
    if(x == n) return 1;
    if(dp.find(x) != dp.end()) return dp[x];
    LL res = 0;
    for(int p = 2; p <= 6; p++) {
        res = (res + dfs(x*p, dp)) % MOD;
    }
    res = res*inv5%MOD;
    return dp[x] = res;
}

int main() {
    scanf("%lld", &n);
    unordered_map<LL, int> dp;
    printf("%lld\n", dfs(1, dp));
    return 0;
}