首页 > 其他分享 >luogu P6276 [USACO20OPEN]Exercise P

luogu P6276 [USACO20OPEN]Exercise P

时间:2023-03-02 16:33:14浏览次数:59  
标签:frac 每个 USACO20OPEN ln luogu 多项式 考虑 质因数 Exercise

题面传送门

首先考虑一个固定排列的答案是什么。考虑它的若干置换环,应该是所有环环长的 LCM,所有数都会转回本来的位置。

现在变成计算所有环的环长的 LCM 的积的问题。注意到这对每个质因数独立,因此我们分别考虑质因数,即我们要计数 \(F_{i,j}\) 表示 \(i\) 这个质因数次数最大值为 \(j\) 的方案数。

直接求不好求,考虑差分变成 \(G_{i,j}\) 表示 \(i\) 这个质因数最大值最多是 \(j\) 的方案数,那么对于每个 \(j\) 只需要考虑质因数中 \(i\) 的次数不超过 \(j\) 的方案数。

我们来考虑一下假设我们知道了排序后环长序列为 \(a_1,a_2,\dots,a_k\),有多少个排列是满足要求的,可以得到是 \(\frac{n!}{\prod a_i}\) ,但是有重复,还要除以每个环长的个数的阶乘。

现在有个问题,我们现在对每个质因数的次数计数,也就是说我们的模数是 \(mod-1\),直接除是不行的。注意到组合数是可以不用乘法逆元计算的,考虑将其变成若干个组合数的乘积。我们一次枚举每个质因数的选的个数,记为质因数 \(k\) 选了 \(j\) 个,之前选了 \(i\) 个,那么应该乘上 \({i+kj\choose i}\prod\limits_{p=1}^{j}{k(j-p+1)-1\choose k-1}(k-1)!\),这样就可以不用乘法逆元了。

再来考虑如何计算每个质因数的答案,直接暴力背包是 \(O(n^3\ln n)\) 的不能过。注意到实际上变化的总共只有 \(O(n\ln \ln n)\) 个,不需要每次 \(O(n)\) 个都放进去背包。也就是说我们让最后乘起来的多项式乘上若干个多项式的逆来得到我们想要的多项式,这里因为每个多项式的零次都是 \(1\) 所以一定有,这样可以把复杂度优化到 \(O(n^2\ln \ln n)\)。

貌似还是过不去。仍然可以注意到每次暴力求逆的时候只有 \(O(\frac{n}{i})\) 个元素是有用的,每次会加进去 \(\frac{n}{i}\) 个元素。又因为 \(\lim\limits_{n\to \infty}\sum\limits_{i=1}^{n}\frac{n^2}{i^2}=\frac{\pi^2}{6}n^2\),所以就是 \(O(n^2)\) 的复杂度。

submission

标签:frac,每个,USACO20OPEN,ln,luogu,多项式,考虑,质因数,Exercise
From: https://www.cnblogs.com/275307894a/p/17172261.html

相关文章

  • 【luogu CF1098D】Eels(结论)
    Eels题目链接:luoguCF1098D题目大意有一个可重集,每次操作会放进去一个数或者取出一个数。然后每次操作完之后,问你对这个集合进行操作,每次选出两个数a,b加起来合并回......
  • luogu P8444 不等价交换法则
    题目传送门分析仔细审了题面,猜想是贪心模拟,下面给出证明:因为只能用元买一个商品,所以要挑贵的买(越贵,换得的商品越多),后令商品尽可能的去换低价格的商品,即把手头所有的商品......
  • [luogu P4705玩游戏] 题解
    P4705玩游戏题解题意概括给出两个序列\(a_0,a_2,\cdotsa_{n-1}\),\(b_0,b_2,\cdotsb_{m-1}\),从两个序列中各等概率的选出两个数\(a_i,b_j\),对于\(k\in[1,t]\)......
  • Solution Luogu6097 子集卷积
    其实是暴力。因为这是模板题,所以模板的前置知识也要讲。前置知识:FWT计算或卷积。这里只需要掌握快速计算或卷积的方法,所以内容较少。如果向了解更多(比如异或卷积)的话......
  • LuoguP5354 [Ynoi2017]由乃的OJ题解
    P5354[Ynoi2017]由乃的OJPreface自己的由乃题一血,写篇题解纪念一下。Description给定一颗\(n\)个结点的树,每个结点都有一个权值\(a_i\)和一个位运算符\(\mathrm{......
  • bash exercise
    3.5.2TildeExpansionecho"~"#onlybeginwithanunquotedcharacterisconsideredatilde-prefixecho~toucht.txtls~+/t.txt#usetheshell......
  • 【题解】Luogu P3939 数颜色
    题目分析:解法一:显然我们可以直接对每一种颜色建一棵线段树,然后剩下的操作就非常简单了。代码:点击查看代码#include<bits/stdc++.h>usingnamespacestd;constint......
  • luogu7764[COCI2016-2017#5] Poklon
    luogu7764[COCI2016-2017#5]Poklonlink莫队解法看了题面之后,便知道能用莫队做。我们知道数组中的数据范围是小于\(10^{9}\)的自然数,而\(1\leN,Q\le5\times10......
  • 【NOIP2001】【Luogu1026】统计单词个数
    problemsolutioncodes//justfortest2#include<iostream>#include<algorithm>#include<cstring>#include<string>usingnamespacestd;intn,m,x,d[210],f......
  • 【NOIP2015】【Luogu2678】跳石头
    problemsolutioncodes//二分答案//QAQ注意:起点和终点也是有石头的w#include<iostream>#include<algorithm>#definemaxn100010usingnamespacestd;intll,n,......