为什么 要建设网站,网站上文章加入音乐是怎么做的,做和别人一样的网站,wordpress邮件有<>啦啦啦#xff0c;今天的考试题 不过原来考试题的n10w 由于我有更好的做法#xff0c;所以我就改成20亿辣 本来先说一说考试题的正解做法的 但是复杂度是O(nlogm)#xff0c;实在是太渣了 所以还是说一说我的做法吧 首先假定都会写裸的DP 我们考虑A,B#xff0c;如果B不… 啦啦啦今天的考试题 不过原来考试题的n10w 由于我有更好的做法所以我就改成20亿辣 本来先说一说考试题的正解做法的 但是复杂度是O(nlogm)实在是太渣了 所以还是说一说我的做法吧 首先假定都会写裸的DP 我们考虑A,B如果B不能转移到A当且仅当A不等于B且A%B0 很容易发现当A是素数时A只不能从1那里转移过来也就是说素数的转移都是一样的 换句话说在状态里当长度一定时以每个素数结尾的方案一定是一样的 这就给了我们一些启发很容易得到结论若两个数的唯一分解式的指数排序后指数序列完全一样 则这两个数的转移一定相同具体证明可以使用数学归纳法 (我离考试结束快15分钟的时候才证明了这个结论结果没时间写了真是悲桑 我们定义转移相同的数为一个等价类可以知道m100000时有160个等价类 这样我们就可以构造一个160*160的矩阵把转移暴力搞出来之后矩阵乘法加速DP 时间复杂度O(160^3logn)这样写的话在cojs上交会小小的T几个点 虽然时间复杂度分析下来是可以跑的过的 但是我们要进行跟时间复杂度同阶的模操作这样会大大减慢程序运算速度 之后我们进行一些分析998244353这个模数2^30相乘2^60 如果我们开unsigned long long那么我们理论上可以进行16次加法之后再做模运算 实际程序实现我采用了每加10次取一次模的方法这样取模的次数大大缩小了 就可以在cojs上通过了 (虽然卡常数很不厚道但是鉴于这道题的思路是我从头到尾YY出来的包括对于常数的优化 所以就这样出在cojs上吧 转载于:https://www.cnblogs.com/joyouth/p/5443638.html
