数学题刷题记录（数学、数论、组合数学）

• P5686 [CSP-S2019 江西] 和积和

简单题，直接将区间求和转换成前缀和，设 (A_i = sum_{i = 1}^n a_i,B_i = sum_{i = 1}^n b_i)，那么式子为：

[sum_{l = 1}^n sum_{r = l}^n (A_r-A_{l-1})(B_r-B_{l-1}) ]

[=sum_{l = 1}^n sum_{r = l}^n A_rB_r-A_rB_{l-1}-A_{l-1}B_r+A_{l-1}B_{l-1} ]

很明显 (O(n)) 枚举右端点 (r)，式子变成：

[sum_{l = 1}^r A_rB_r-A_rB_{l-1}-A_{l-1}B_r+A_{l-1}B_{l-1} ]

如何快速算出这个式子？

我们有：

[sum_{l = 1}^r A_rB_r-A_rB_{l-1}-A_{l-1}B_r+A_{l-1}B_{l-1}=sum_{l = 1}^r A_rB_r-sum_{l = 1}^r A_rB_{l-1}-sum_{l = 1}^r A_{l-1}B_r+sum_{l = 1}^r A_{l-1}B_{l-1} ]

于是可以将四个单项式分类讨论。

(A_rB_r) 很好处理，直接算，由于 (l) 有 (r) 个取值，所以是 (rA_rB_r)。

(A_rB_{l-1}) 很明显 (A_r) 没有问题，但 (B_{l-1}) 需要预处理 (B) 的前缀和，也就是前缀和的前缀和。

(A_{l-1}B_r) 同理。

(A_{l-1}B_{l-1}) 很显然需要另外维护两前缀和之积的前缀和。

代码：

#include<bits/stdc++.h> using namespace std; const int mod = 1e9+7; const int N = 5e5+5; int a[N],b[N]; long long suma[N],sumb[N],prea[N],preb[N],mul[N]; signed main() { 	ios::sync_with_stdio(0); 	cin.tie(0); 	cout.tie(0); 	int n; 	cin >> n; 	for(int i = 1;i<=n;++i) 	{ 		cin >> a[i]; 		suma[i] = (suma[i-1]+a[i])%mod; 		prea[i] = (prea[i-1]+suma[i])%mod; 	} 	for(int i = 1;i<=n;++i) 	{ 		cin >> b[i]; 		sumb[i] = (sumb[i-1]+b[i])%mod; 		preb[i] = (preb[i-1]+sumb[i])%mod; 		mul[i] = (mul[i-1]+1ll*suma[i]*sumb[i]%mod)%mod; 	} 	long long sum = 0; 	for(int i = 1;i<=n;++i) 	{ 		long long A = i*suma[i]%mod*sumb[i]%mod,B = suma[i]%mod*preb[i-1]%mod,C = sumb[i]%mod*prea[i-1]%mod,D = mul[i-1]; 		sum = (sum+(((A-B+mod)%mod-C+mod)%mod+D)%mod)%mod; 	} 	cout << sum; 	return 0; } 

• P8557 炼金术（Alchemy）

对于每一个金属，它会被任意 (1 sim k) 个熔炉炼烧出来，所以方案数为 (C_k^1+C_k^2+C_k^3+dots+C_k^{k-1}+C_k^k = sum_{i = 1}^k C_k^i)，根据二项式定理，((1+1)^k = sum_{i = 0}^k C_k^ix^i y^{n-i} = sum_{i = 0}^k C_k^i)，而 (C_k^0 = 1)，所以 (sum_{i = 1}^k C_k^i = 2^k-1)，那么有 (n) 个金属，答案就是 ((2^k-1)^n)，快速幂计算即可。

代码：

#include<bits/stdc++.h> using namespace std; const int mod = 998244353; int fast_pow(int a,int b) { 	int ans = 1; 	while(b) 	{ 		if(b&1) 		{ 			ans = 1ll*ans*a%mod; 		} 		a = 1ll*a*a%mod; 		b>>=1; 	} 	return ans; } signed main() { 	ios::sync_with_stdio(0); 	cin.tie(0); 	cout.tie(0); 	int n,k; 	cin >> n >> k; 	cout << fast_pow((fast_pow(2,k)-1+mod)%mod,n); 	return 0; } 

• P6191 [USACO09FEB] Bulls And Cows S

这题我根本不是用数学方式做的。
递推，设 (fg_i) 表示第 (i) 头是公牛时的方案数，(fn_i) 表示第 (i) 头是奶牛时的方案数，则状态转移方程为：

[fn_i = fn_{i-1}+fg_{i-1} ]

[fg_i = fg_{i-k-1}+fn_{i-k-1}(i>k+1) ]

[fg_i = 1(i le k+1) ]

迎刃而解。

代码：

#include<bits/stdc++.h> using namespace std; const int mod = 5000011; const int N = 1e5+5; int a[N]; int fn[N],fg[N]; signed main() { 	ios::sync_with_stdio(0); 	cin.tie(0); 	cout.tie(0); 	int n,k; 	cin >> n >> k; 	fn[1] = 1; 	fg[1] = 1; 	for(int i = 2;i<=n;++i) 	{ 		fn[i] = (fn[i-1]+fg[i-1])%mod; 		if(i>k+1) 		{ 			fg[i] = (fg[i-k-1]+fn[i-k-1])%mod; 		} 		else 		{ 			fg[i] = 1; 		} 	} 	cout << (fn[n]+fg[n])%mod;  	return 0; } 

• P8183 [USACO22FEB] Sleeping in Class B

首先不管怎么合并最后数组中所有数的和都是一样的，所以可以算出总和 (sum)，然后找到 (sum) 的所有约数，从小到大排个序，由于每次合并数组长度减少 (1)，所以我们知道拿原本数组长度减去合并后的数组长度就是合并的次数，那我们肯定使长度越大越好，由于约数已经倒序排序形成数组 (b)，我们倒着扫，将 (b_i) 看成长度，那么 (frac{sum}{b_i}) 就是最终合并之后数组中统一的数，然后扫一遍原数组 (a) 检测一下即可。

时间复杂度 (O(nsqrt{n}))。

代码：

#include<bits/stdc++.h> using namespace std; const int N = 1e6+5; int a[N]; int ans[N]; signed main() { 	ios::sync_with_stdio(0); 	cin.tie(0); 	cout.tie(0); 	int _; 	cin >> _; 	while(_--) 	{ 		int n,sum = 0,cnt = 0,biao = 1; 		cin >> n; 		for(int i = 1;i<=n;++i) 		{ 			cin >> a[i]; 			sum+=a[i]; 			if(i>1&&a[i]!=a[i-1]) 			{ 				biao = 0; 			} 		} 		if(biao) 		{ 			cout << 0 << 'n'; 		} 		for(int i = 1;i*i<=sum&&i<=n;++i) 		{ 			if(sum%i == 0) 			{ 				ans[++cnt] = i; 				int s = sum/i; 				if(s!=i&&s<=n) 				{ 					ans[++cnt] = s; 				} 			} 		} 		sort(ans+1,ans+cnt+1); 		for(int i = cnt;i;--i) 		{ 			int num = sum/ans[i]; 			int summ = 0; 			int flag = 1; 			int res = 0; 			for(int j = 1;j<=n;++j) 			{ 				if(summ+a[j]<=num) 				{ 					summ+=a[j]; 				} 				else 				{ 					flag = 0; 					break; 				} 				if(summ == num) 				{ 					++res; 					summ = 0; 				} 			} 			if(flag&&res == ans[i]) 			{ 				cout << n-ans[i] << 'n'; 				break; 			} 		} 	} 	return 0; } 

-P10411 「QFOI R2」树色尤含残雨

首先根据唯一分解定理，可得：

[x = prod_{i = 1}^k p_i^{q_i},p_i in prime,q_i in N^+ ]

然后分类讨论，首先你会发现当 (x) 有因子是完全平方数（也就是分解之后 (exists i(1 le i le n)q_i>1)），那么答案除了在只有一个质因数的时候为 (x) 其他情况都是 (1)，不分奇偶，为啥？很简单，因为就算质因子数量为奇数，也可以将其中一个拆分，变成偶数。那么如果 (x) 没有因子是完全平方数，那么就要看奇偶了，奇数就取最小质因数（简单贪心思想），偶数就是 (1)，原理简单，不再敖述。

代码：

#include<bits/stdc++.h> using namespace std;  signed main() { 	ios::sync_with_stdio(0); 	cin.tie(0); 	cout.tie(0); 	int n,minn = 0,num = 0,shu = 0; 	cin >> n; 	int q = n; 	for(int i = 2;i*i<=n;++i) 	{ 		if(n%i == 0) 		{ 			if(!minn) 			{ 				minn = i; 			} 			++num; 			int cnt = 0; 			while(n%i == 0) 			{ 				++cnt; 				n/=i; 			} 			if(cnt>1) 			{ 				++shu; 			} 		} 	} 	if(n>1) 	{ 		if(!minn) 		{ 			minn = n; 		} 		++num; 	} 	if(!shu) 	{ 		if(num&1) 		{ 			cout << minn; 		} 		else 		{ 			cout << 1; 		} 	} 	else 	{ 		if(num == 1) 		{ 			cout << q; 		} 		else 		{ 			cout << 1; 		} 	} 	return 0; } 

• P9148 除法题

很显然题目的数据范围 (n le 5 times 10^3)，复杂度显然是 (O(n^2)) 或者 (O(n^2 log n))，很显然这题是数学题，时限又如此之大，很明显能猜出复杂度为 (O(n^2 log n)) 级别，而说到 (log) 在数学中很容易想到调和级数，那么这题就很显然了，题目要求的东西是：

[sum_{a in A}sum_{b in A}sum_{c in A}lfloor frac{a}{b}rfloorlfloor frac{a}{c}rfloorlfloor frac{b}{c}rfloor ]

很显然只有在 (a>b>c) 的时候有贡献，那么考虑枚举枚举 (b,c)，复杂度 (O(n^2))，然后充分利用调和级数，枚举 (s) 表示 (lfloorfrac{a}{c}rfloor) 那么 (a) 能取的合法值就是一个区间，记这个区间为 ([l,r])，假设能 (O(1)) 计算 ([l,r]) 的值域中 (lfloorfrac{a}{b}rfloor) 的和，那么迎刃而解，复杂度为 (O(n^2 log n))，然而 (O(1)) 处理这个区间的贡献很容易，前缀和预处理即可。

那么最后要求的其实就是：

[sum_{b in A}sum_{c in A}lfloorfrac{b}{c}rfloorsum_{s = 1}^{frac{max_{i = 1}^n A_i}{c}}ssum_{a in A,l le a le r}lfloorfrac{a}{b}rfloor ]

(l) 和 (r) 的赋值写不下了，放这里：

[l = max(b+1,s times c) ]

[r = min(max_{i = 1}^n A_i,(s+1) times c-1) ]

然后还要注意三点：

• 首先 (l) 和 (r) 是值域，而并非下标，而前缀和很明显不能太方便地维护值域，所以要将 (l,r) 转化成下标（最好预处理解决）。
• 在算出 (l) 的时候记得特判一下 (l>max_{i = 1}^nA_i) 的情况和换算成下标后的 (l'>r') 的可能性（我也不确定第二个要不要判，但判一下总没错，并且第一个是一定要判的）。
• (l,r) 的转下标方式不一样，一个是 lower_bound，一个是 upper_bound。

代码：

#include<bits/stdc++.h> using namespace std; const int N = 5e3+5; const long long mod = 1ll<<32; int b[N],pre[N][N],c[N],a[N]; signed main() { 	ios::sync_with_stdio(0); 	cin.tie(0); 	cout.tie(0); 	int n,maxx = 0; 	cin >> n; 	for(int i = 1;i<=n;++i) 	{ 		cin >> a[i]; 		maxx = max(maxx,a[i]); 	} 	sort(a+1,a+n+1); 	for(int i = 1;i<=n;++i) 	{ 		for(int j = 1;j<=maxx;++j) 		{ 			pre[i][j] = pre[i-1][j]+a[i]/j; 		} 	} 	for(int i = 1;i<=maxx;++i) 	{ 		b[i] = lower_bound(a+1,a+n+1,i)-a; 		c[i] = upper_bound(a+1,a+n+1,i)-a-1; 	} 	long long ans = 0; 	for(int i = 1;i<=n;++i) 	{ 		for(int j = 1;j<i;++j) 		{ 			int cc = a[i]/a[j]; 			int MAX = maxx/a[j]; 			long long sum = 0; 			for(int k = 1;k<=MAX;++k) 			{ 				int ll = max(a[i]+1,k*a[j]),rr = min(maxx,(k+1)*a[j]-1); 				if(ll>maxx) 				{ 					continue; 				} 				int l = b[ll],r = c[rr]; 				if(l>r) 				{ 					continue; 				} 				sum = (sum+k*(pre[r][a[i]]-pre[l-1][a[i]])%mod)%mod; 			} 			ans = (ans+cc*sum%mod)%mod; 		} 	} 	cout << ans; 	return 0; } 

• P12142 [蓝桥杯 2025 省 A] 黑客

虽然此题有亿点坑，但也真不至于绿。

思路很显然，设 (n times m+2 = n)，那么矩阵大小 (a times b = n-2)，也就是说 (n bmod a = 0,n bmod b = 0)，那么剩余的数能组成的方案就是：

[prod_{i = 1}^{max_{k = 1}^n a_k} num_i ]

(num_i) 指的是 (i) 出现的次数（不能包含 (a) 和 (b) 这两个数），那么显然这么做的时间复杂度是 (O(nv))，(v) 为值域，显然过不去，那么考虑到每次也最多改两个数的位置，其实是可以通过简单推式子计算算出来的，没必要每次都跑一遍，先用一个变量 (res) 算出原本的 (prod_{i = 1}^{max_{k = 1}^n a_k} num_i)，然后首先对于取了 (a) 这个数（这个 (a) 不是数组），那其实让 (res) 除以 (num_a) 就行，然后让 (num_a) 减少 (1)，然后对于 (b) 也是同理，这题就搞定了，带取模质数的除法，用费马小定理就能搞定。

本题坑点：

• 别忘了两个矩阵的行数和列数如果全部一样，那就算重了。

• 别忘了枚举约数只会枚举到 (sqrt{n-2})，记得算行和列调换后的结果。

• 算行和列调换时，要注意 (a = b) 的特殊情况。

代码：

#include<bits/stdc++.h> using namespace std; const int mod = 1e9+7; const int N = 5e5+5; int num[N]; int jie[N]; int a[N]; int vis[N]; inline int fast_pow(int a,int b) { 	int ans = 1; 	while(b) 	{ 		if(b&1) 		{ 			ans = 1ll*ans*a%mod; 		} 		a = 1ll*a*a%mod; 		b>>=1; 	} 	return ans; } signed main() { 	ios::sync_with_stdio(0); 	cin.tie(0); 	cout.tie(0); 	int n,maxx = 0; 	cin >> n; 	for(int i = 1;i<=n;++i) 	{ 		cin >> a[i]; 		maxx = max(maxx,a[i]); 		++num[a[i]]; 	} 	jie[0] = 1; 	for(int i = 1;i<=n;++i) 	{ 		jie[i] = 1ll*jie[i-1]*i%mod; 	} 	int res = 1; 	for(int i = 1;i<=maxx;++i) 	{ 		if(num[i]) 		{ 			res = 1ll*res*jie[num[i]]%mod; 		} 	} 	res = fast_pow(res,mod-2); 	sort(a+1,a+n+1); 	int sum = 0; 	for(int i = 1;1ll*a[i]*a[i]<=n-2&&i<=n;++i) 	{ 		if((n-2)%a[i] == 0&&!vis[a[i]]) 		{ 			vis[a[i]] = 1; 			int j = (n-2)/a[i]; 			int ji = 1ll*jie[n-2]*res%mod*num[a[i]]%mod; 			--num[a[i]]; 			ji = 1ll*ji*num[j]%mod; 			sum = (sum+ji)%mod; 			if(a[i]!=j) 			{ 				vis[j] = 1; 				sum = (sum+ji)%mod; 			} 			++num[a[i]]; 		} 	} 	cout << sum; 	return 0; } 

• P1680 奇怪的分组

显然组合数学。

先将 (n) 减去所有的 (C_i)，那么问题就变成了将 (n) 个球放入 (m) 个盒子（盒子不能为空）的方案数，显然可以用隔板法求。

所谓隔板法，就是解决盒子放球问题的经典模型，我们先考虑盒子可以为空的情况，所谓隔板就是在 (n) 个物品/球中放上隔板，很显然要分 (m) 组就是 (m-1) 个隔板，如图：

★★∣★★★∣★★★ n = 8,k = 3 

那么方案数就是 (C_{n+k-1}^{k-1}) 就是相当于从 (n+k-1) 个隔板和球中选 (k-1) 个隔板的方案数，盒子可以为空时就解决了，那盒子不为空咋办？很简单。

我们先给每组分配一个物品，只剩 (n-1) 个物品，我们要在这 (n-1) 个物品中选择 (k-1) 个隔板，所以是 (C_{n-1}^{k-1})。

这题显然是第二种，于是预处理阶乘的逆元即可轻松解决。

#include<bits/stdc++.h> using namespace std; const int mod = 1e9+7; const int N = 1e6+5; int jie[N]; inline int fast_pow(int a,int b) { 	int ans = 1; 	while(b) 	{ 		if(b&1) 		{ 			ans = 1ll*ans*a%mod; 		} 		a = 1ll*a*a%mod; 		b>>=1; 	} 	return ans; } signed main() { 	ios::sync_with_stdio(0); 	cin.tie(0); 	cout.tie(0); 	int n,m; 	cin >> n >> m; 	for(int i = 1;i<=m;++i) 	{ 		int x; 		cin >> x; 		n-=x; 	} 	jie[0] = 1; 	for(int i = 1;i<=n;i++) 	{ 		jie[i] = 1ll*jie[i-1]*i%mod; 	} 	--n; 	--m; 	cout << 1ll*jie[n]*fast_pow(jie[n-m],mod-2)%mod*fast_pow(jie[m],mod-2)%mod; 	return 0; } 

• P5148 大循环

很显然 (f(q)) 是个很没用而且碍眼并且值又固定的东西，那么预处理算出 (f(q))，然后问题转化成求长度为 (k) 值域为 (1 sim n) 的序列中单调不降的序列个数，那么仔细思考，对于从 (n) 中任选 (k) 个，重排一遍一定可以，所以说就是 (C_n^k)，答案为 (C_n^k f(q))。

代码：

#include<bits/stdc++.h> using namespace std; const int mod = 1e9+7; const int N = 5e5+5; int a[N]; int jie[N]; inline int fast_pow(int a,int b) { 	int ans = 1; 	while(b) 	{ 		if(b&1) 		{ 			ans = 1ll*ans*a%mod; 		} 		a = 1ll*a*a%mod; 		b>>=1; 	} 	return ans; } signed main() { 	ios::sync_with_stdio(0); 	cin.tie(0); 	cout.tie(0); 	int n,m,k,f = 0; 	long long q; 	cin >> n >> m >> k >> q; 	q%=mod; 	for(int i = 0;i<=m;++i) 	{ 		cin >> a[i]; 		f = (f+1ll*a[i]*fast_pow(q,i)%mod)%mod; 	} 	jie[0] = 1; 	for(int i = 1;i<=n;++i) 	{ 		jie[i] = 1ll*jie[i-1]*i%mod; 	} 	cout << 1ll*jie[n]*fast_pow(jie[n-k],mod-2)%mod*fast_pow(jie[k],mod-2)%mod*f%mod; 	return 0; } 

• P5684 [CSP-J2019 江西] 非回文串

首先容斥，非回文串个数等于总个数减去回文串个数，总个数显然是 (n!)，那么回文串个数怎么算呢？首先用 (num) 数组记录每个字母出现次数，那么对于每个字母 (x) 先不考虑它本身的排列，那么非回文串个数就是：

[frac{n}{2}!prod_{i = 1}^{26}frac{1}{frac{num_i}{2}!} ]

加上每个字母本身的排列个数：

[frac{n}{2}!prod_{i = 1}^{26}frac{num_i!}{frac{num_i}{2}!} ]

最终答案：

[n!-frac{n}{2}!prod_{i = 1}^{26}frac{num_i!}{frac{num_i}{2}!} ]

记得特判本身不存在回文串的情况。

#include<bits/stdc++.h> using namespace std; const int mod = 1e9+7; const int N = 1e5+5; int num[N]; int jie[N]; char s[N]; inline int fast_pow(int a,int b) { 	int ans = 1; 	while(b) 	{ 		if(b&1) 		{ 			ans = 1ll*ans*a%mod; 		} 		a = 1ll*a*a%mod; 		b>>=1; 	} 	return ans; } signed main() { 	ios::sync_with_stdio(0); 	cin.tie(0); 	cout.tie(0); 	int n; 	cin >> n; 	cin >> s+1; 	jie[0] = 1; 	for(int i = 1;i<=n;++i) 	{ 		jie[i] = 1ll*jie[i-1]*i%mod; 		++num[s[i]-'a']; 	} 	int cnt = 0; 	for(int i = 0;i<26;i++) 	{ 		if(num[i]&1) 		{ 			++cnt; 		} 	} 	if(cnt>1) 	{ 		cout << jie[n]; 		return 0; 	} 	int res = 1; 	for(int i = 0;i<26;i++) 	{ 		if(!num[i]) 		{ 			continue; 		} 		res = 1ll*res*jie[num[i]]%mod*fast_pow(jie[num[i]>>1],mod-2)%mod; 	} 	cout << (jie[n]-1ll*jie[n>>1]*res%mod+mod)%mod; 	return 0; }