AT_abc300_e 题解

yhy-trh / 2023-05-03 / 原文

一、题目描述：

　　你有一个骰子，数字 $1$~$6$ 可以被等概率扔到。

　　初始时有一个数 $ans=1$。

　　当扔到数字 $x$ 时，$ans=ans \times x$。

　　给你一个数字 $n$ ，求 $ans$ 能等于 $n$ 的概率。

　　$n<=1e18$。答案对 $998244353$ 取模。

二、解题思路：

　　当扔到 $1$ 时，相当于没扔，所以可以视为 5 个数

　　求出 $n$ 的质因数 $2$，$3$，$5$ 的个数，设有 $ans_2$ 个 $2$，$ans_3$ 个 $3$，$ans_5$ 个 $5$。

　　一个 $6$ 相当于一个 $2$ 和一个 $3$ 相乘，一个 $4$ 相当于两个 $2$ 相乘。

　　枚举 $4$ 的数量，再枚举 $6$ 的数量，再套组合数板子：多重集的排列数量。

　　最后求和。需要用到逆元，阶乘。时间复杂度 $O(log^3n)$，可以通过。

三、完整代码：

 1 #include<iostream>
 2 #define ll long long
 3 #define mod 998244353
 4 using namespace std;
 5 ll n,t2=1,rans,jc[100];
 6 ll ans2,ans3,ans5;
 7 ll qsm(ll base,ll p)
 8 {
 9     ll ans=1;
10     while(p)
11     {
12         if(p&1)    ans*=base,ans%=mod;
13         base*=base,base%=mod,p>>=1;
14     }
15     return ans;
16 }
17 int main()
18 {
19     cin>>n;jc[0]=1;
20     while(n&&n%2==0)
21         ans2++,n/=2;
22     while(n&&n%3==0)
23         ans3++,n/=3;
24     while(n&&n%5==0)
25         ans5++,n/=5;
26     if(n!=1)
27     {
28         cout<<0<<'\n';
29         return 0;
30     }
31     for(ll i=1;i<=70;i++)
32         jc[i]=jc[i-1]*i%mod;
33     for(ll i=0;i<=min(ans2,ans3);i++)
34         for(int j=0;j*2<=ans2-i;j++)
35         {
36             ll t=ans2+ans3+ans5-i-j;
37             t2=jc[t]*qsm(qsm(5,t),mod-2)%mod;
38             t2*=qsm(jc[i],mod-2),t2%=mod;
39             t2*=qsm(jc[j],mod-2),t2%=mod;
40             t2*=qsm(jc[ans5],mod-2),t2%=mod;
41             t2*=qsm(jc[ans3-i],mod-2),t2%=mod;
42             t2*=qsm(jc[ans2-i-j*2],mod-2),t2%=mod;
43             rans+=t2,rans%=mod;
44         }
45     cout<<rans<<'\n';
46     return 0;
47 }