D1T4 小学生计数题

题目

作为 GDOI 的组题人，小 Y 需要整理手中已有的题目，考虑它们的难度以及所考察的知识点，然后将它们组成数套题目。

小 Y 希望先能组出第一套题目，为了整套题目具有良好的区分度，在一套题目中：

• 所有题目的难度需要能排成等差数列；（也就是说，若将所有题目按难度从小到大排序，那么每相邻两题的难度的差相等，这个差叫做公差）
• 每道题目的难度都是公差的倍数，公差不为 0；
• 需要有不少于 \(L\) 道题，不多于 \(R\) 道题。

现在小 Y 手里已经有了 \(m\) 道题目，其中难度为 \(a_i\) 的题有 \(c_i\) 道 \((1 ≤ i ≤ n)\)。

小 Y 希望能够知道，他有多少种不同的方式能够组出一套题目。

在这道题目中，我们认为两种组题方式不同当且仅当 \(?k(1 ≤ k ≤ m)\)，使得一种方案包含第 \(k\) 道题而另一种方案不包含。

由于答案可能很大，输出答案对 \(998244353\) 取模。

思路

先不考虑题目数量，我们把所有等差数列抽出来。满足这些等差数列都不满足一个完全包含另一个。

我们把这种等差数列定义为特殊等差数列。

那么此时对于任意一种难度 \(a_i\)，它最多会被多少个特殊等差数列包含？

显然，对于所有特殊等差数列，其公差必然互不相同。

于是，这种难度 \(a_i\)，它的因数个数必然小于100个（打个程序可以验证），所以包含它的特殊等差数列个数必然小于100个。

然后我们就可以把所有特殊等差数列处理出来了。上面的时间复杂度是 \(O(n\log n)\)

我们把这些抽出来的等差数列分别处理，看看其有多少个符合要求的等差数列。

暴力的思想使枚举开头和结尾，然后再暴力循环一遍求其方案，复杂度为 \(O(n^3)\)，总复杂度为 \(O(n^4\log n)\)。

显然，最后一重暴力循环不必要，我们可以求个乘积前缀和，然后套费马小定理求逆元再求乘积，复杂度 \(O(n^3\log n)\)。

然后我们发现逆元也可以再做一个前缀和，然后再省掉一重循环，变为 \(O(n^2\log n\log n)\)，还有一个 \(\log\) 是因为求逆元有个快速幂需要 \(\log\)。（我不知道线性求逆元在此题可不可行，感兴趣可以试一试）

时间复杂度看起来会爆，然而，每个特殊等差数列。假如其个数多，那么长度小。假如个数小，长度多。因此均摊下来是 \(O(n\log n\log n)\) 的。

官方数据似乎不需要逆元前缀和的优化，但民间数据卡了。

Code

#include
using namespace std;
#define int long long
inline int read(){int f=1,x=0;char ch=getchar();while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define N 200010
//#define M
//#define mo
struct node
{
	int x, y; 
	bool operator <(const node &A) const
	{
		return yv[N]; 
int w[N], f[N], c[N], ans; 
priority_queueq; 
//priority_queueq; 

signed main()
{
	
	n=read(); 
	for(i=1; i<=n; ++i) w[i]=read(); 
	for(i=2; i<=n; ++i) 
	{
		f[i]=read(); c[f[i]]=1; 
//		printf("%lld\n", f[i]); 
		v[f[i]].push_back(i); 
	} 
	p.x=1; p.y=w[1]; q.push(p); ans=w[1]; 
	while(!q.empty())
	{
		p=q.top(); q.pop(); 
//		printf("%lld\n", p.x); 
		if(!c[k=p.x]) return printf("%lld\n", ans), 0; 
		for(i=0; i