首页 > 其他分享 >AT_abs300_e 题解

AT_abs300_e 题解

时间:2023-04-29 22:33:52浏览次数:40  
标签:题解 ll while base && ans abs300 mod

一、题目描述:

  你有一个骰子,数字 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             
44             rans+=t2,rans%=mod;
45         }
46     cout<<rans<<'\n';
47     return 0;
48 }

四、写题心得:

  很好的一道题,对我来说有难度。这次是完全自己想出来的,很高兴,可惜是在比赛后十分钟写出来的 qwq!不过还是加油吧!拜拜!

标签:题解,ll,while,base,&&,ans,abs300,mod
From: https://www.cnblogs.com/yhy-trh/p/17364576.html

相关文章

  • 皇后游戏 题解
    luoguP2123题目描述皇后有\(n\)位大臣,每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临,皇后决定为\(n\)位大臣颁发奖金,其中第\(i\)位大臣所获得的奖金数目为第\(i-1\)位大臣所获得奖金数目与前\(i\)位大臣左手上的数的和的较大值再加上第\(i\)位大臣右手......
  • 题解
    D.RangeandPartition1800思维https://codeforces.com/contest/1631/problem/D题解:由于严格大于,故其最终前缀和s[n]>=k,而当s[n]>=k,s[0]=0,每步至多下降1,故其中必有至少k个点满足s[i]=x(1<=x<=k),故符合题意,故只需双指针找出最小的满足题意的区间即可。#include<bits/stdc++......
  • 4 月 27 日测试题解
    4月27日测试题解最短路专场T1\({\color{green}{\text{100pts}}}\text{/100pts}\)题意给出\(m\)个变量与\(n\)个约束,每个约束形如以下三种中的一种;\(x_i-x_j\lew\)\(x_i-x_j\gew\)\(x_i-x_j=w\)有\(q\)个询问,每个询问为形如\((x_i,x_j)\)的二元......
  • 4 月 21 日测试题解
    4月21日测试题解T1\({\color{green}{\text{100pts}}}\text{/100pts}\)题意给出平面上的两条线段,求线段之间的距离。\(\text{|线段端点坐标|}\le10^4\)。思路一开始想的是分讨,但是又怕自己写挂了,所以就写了三分套三分。至少这个不怕少讨论一个情况。既然是三分套三分,......
  • 问题解决:Component name "xxx" should always be multi-word vue/multi-word-compone
    如题,原因是单个单词命名时语法检测无法通过,可以在导出组件时通过name属性给组件名加一个后缀,比如Component。<script>exportdefault{//当组件名为一个单词时,语法检查是无法通过的,可以设置name的值为2个单词来规避检查。name:'HomeComponent'}<......
  • IdentityServer4 问题解决
    RedirectUris={"https://localhost:7098/signin-oidc"},PostLogoutRedirectUris={"https://localhost:7098/signout-callback-oidc"},服务端添加这个 RequirePkce=false,添加这一句......
  • open3d Reconstruction system 问题解决
    1.https://github.com/luckyluckydadada/Azure-Kinect-DK-3D-reconstruction 2.open3d版本:0.14.10.16.00.17.0会报错:open3d.cuda.pybind.piplines.odommetry.OdomtryOptionbojecthasnoattribute'max_depth_diff' 3.结果问题一:    根据......
  • [P4145 上帝造题的七分钟 2 / 花神游历各国]题解
    P4145上帝造题的七分钟2/花神游历各国题目描述分析一开始在思考有没有一个数学公式来处理每一个开方的操作但发现数据的\(\le10^{12}\)那么最多开六次就变成1了(突破口)这样每一个数的有用操作只有6次其他就全部是1很显然,我们可以去记录每一段是否全为1再用线段树、分......
  • CodeForces-858#C 题解
    正文♦最坏时间复杂度:\(\mathcal{O}(\lvertS\rvert)\)本题十分简单,但请注意两个条件要同时满足。因为要求分割的次数越少越好,所以只要连续的辅音字母长度不大于2就不需要分割。由于辅音字母太多,只需要标记元音字母即可。#include<iostream>#include<string>#include<cst......
  • 【题解】P3920 [WC2014]紫荆花之恋
    思路点分树+根号重构+*高速平衡树。点分树的两种常见用法无非是直接做和路径有关的暴力还有处理这种有关单点和整树的问题,后者的另一个经典题目是P3241[HNOI2015]开店。回到这个题目,处理路径考虑先上点分治,暂时不考虑强制在线的限制。因为每次加上一个新点,所以可以考......