[ABC300E] Dice Product 3 题解

FFTotoro · 2023-05-01 09:38:14 · 题解

前言

赛时通过快速切这个题小号 5 场上青 /oh。

解法

本题需要使用记忆化搜索算法。

令 p(x) 为骰子转到 x 的概率，考虑 p(x) 怎么由更小的状态转移而来：

• 首先，p_1=1，因为整数一开始就是 1；骰子显示 1 时对答案并没有实质上的影响，可以忽略；

• 如果 x\equiv0\pmod2，那么有可能骰子上一次投到 2；即有 \dfrac{1}{5} 的概率 \dfrac{x}{2} 转化为 x；

• 如果 x\equiv0\pmod3，那么有可能骰子上一次投到 3；即有 \dfrac{1}{5} 的概率 \dfrac{x}{3} 转化为 x；

  \vdots

• 如果 x\equiv0\pmod6，那么有可能骰子上一次投到 6；即有 \dfrac{1}{5} 的概率 \dfrac{x}{6} 转化为 x；

所以，我们有：

转移过程用一个 map 记录一下即可。

放代码：

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int mod=998244353;
int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=r%mod*a%mod;
    a=a%mod*a%mod; b>>=1;
  }
  return r;
}
int inv(int x){return qpow(x,mod-2);}
map<int,int> m;
int f(int n){
  if(m[n])return m[n];
  for(int i=2;i<=6;i++)
    if(!(n%i))(m[n]+=f(n/i)*inv(5)%mod)%=mod;
  return m[n];
}
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin>>n; m[1]=1; int x=n;
  while(x>1)x/=2; while(x>1)x/=3; while(x>1)x/=5;
  if(x>1)cout<<"0\n";
  else cout<<f(n)<<endl;
  return 0;
}