本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16180001.html

D1T4 小学生计数题

题目

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

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

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

现在小 Y 手里已经有了 mm 道题目，其中难度为 aia_i 的题有 cic_i 道 (1≤i≤n)(1 ≤ i ≤ n)。

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

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

由于答案可能很大，输出答案对 998244353998244353 取模。

思路

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

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

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

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

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

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

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

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

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

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

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<bits/stdc++.h>
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 800010
//#define M
#define mo 998244353
struct node
{
	int x, y; 
}ax[N]; 
int n, m, i, j, k, T; 
int a[N], b[N], c[N], d[N], x[N], s[N], mp[N]; 
int ans, L, R, sx[N], sy[N]; 
map<int, int>dp[N]; 
int sum, anss;  

bool cmp(node x, node y)
{
	return x.x<y.x; 
}

int kuai(int a, int b)
{
	int ans=1; 
	while(b)
	{
		if(b&1) ans=ans*a%mo; 
		a=a*a%mo; 
		b>>=1; 
	}
	return ans; 
}

//int chu(int a, int b)
//{
//	return a*kuai(b, mo-2)%mo; 
//}

//int pan(int l, int r, int k)
//{
//	int i, j, ans=0; 
//	for(i=1; i<=r; ++i)
//		for(j=i-k+1; j<=i; ++j) 
//		{
//			ans+=chu(s[i], s[j-1]); 
//			ans=(ans+mo)%mo; 
//		}
//	return ans; 
//}

int panp(int n, int l, int r)
{
	int  i, j, ans=0; 
	for(i=l; i<=n; ++i)
	{
		sum=(sy[i-l]-sy[max(1ll, i-r+1)-2])%mo; 
		ans+=s[i]*sum%mo; 
		ans=(ans+mo)%mo;  
	}
		
	return ans; 
}

void check(int i, int k)
{
	int m=0, j; 
	while(i) d[++m]=i, i=dp[i][k]; 
	for(i=1, j=m; i<=m; ++i, --j) x[i]=d[j]; 
//	for(i=1; i<=m; ++i) printf("%lld ", a[x[i]]); 
//	printf(":%lld\n", k); 
	for(i=1; i<=m; ++i) d[i]=c[x[i]]; 
	for(i=s[0]=1; i<=m; ++i) s[i]=s[i-1]*d[i]%mo; 
	for(i=0; i<=m; ++i) sx[i]=kuai(s[i], mo-2)%mo; 
	for(i=0; i<=m; ++i) sy[i]=((i-1==-1 ? 0 : sy[i-1])+sx[i])%mo; 
//	for(i=1; i<=m; ++i) printf("%lld ", s[i]); 
//	printf("\n"); 
//	ans+=(pan(1, m, R)-pan(1, m, L-1)); 
	ans+=panp(m, L, R); 
	ans=(ans%mo+mo)%mo; 
}

signed main()
{
//	freopen("counting.in", "r", stdin);
//	freopen("counting.out", "w", stdout);
//	freopen("tiaoshi.in", "r", stdin);
//	freopen("tiaoshi.out", "w", stdout);
	n=read(); m=read(); L=read(); R=read(); 
	for(i=1; i<=n; ++i) 
		ax[i].x=read(), ax[i].y=read(); 
	sort(ax+1, ax+n+1, cmp); 
	for(i=1; i<=n; ++i)
		a[i]=ax[i].x, c[i]=ax[i].y; 
//	for(i=1; i<=n; ++i) printf("%lld ", a[i]); 
	for(i=1; i<=n; ++i) mp[a[i]]=i; 
	for(i=1; i<=n; ++i)
	{
//		if(a[i]==0) continue; 
		m=0; 
		if(a[i]==0) 
		{
			for(j=2; j<=n; ++j) 
				dp[j][a[j]]=1; 
			continue; 
		}
		for(j=1; j*j<=a[i]; ++j)
			if(a[i]%j==0)
			{
				b[++m]=j; b[++m]=a[i]/j; 
				if(j*j==a[i]) --m; 
			} 
		sort(b+1, b+m+1); 
//		printf("%lld:", a[i]); 
		for(j=1; j<=m; ++j)
		{
//			printf("%lld ", b[j]); 
			if(k=mp[a[i]+b[j]]) dp[k][b[j]]=i; 
			else check(i, b[j]); 
		}
//		printf("\n"); 
	}
	printf("%lld", ans); 
	return 0;
}



4.25更新：此题需要特判一下 ai=0a_i=0 的情况（官方数据没卡，但万恶的民间出题人卡了）

总结

首先对于这道题，首先要想到的是制造特殊等差数列，因为很多情况就可以归到一起来考虑了。

然后是对于题目中等差数列公差的特殊定义可以去思考，然后发现特殊等差数列个数受限于数的因数个数。

然后后面的优化就是凭经验了。对于多次求逆元，可以考虑逆元前缀和进行优化。