Luogu P6300 悔改

link
 

题解

设 (f_x) 表示组成 (x) 的个数，(b_i) 表示长度为 (i) 的木棍的出现次数。则 (f_x = leftlfloordfrac{1}{2}sumlimits_{i=1}^x min{b_i,b_{x-i}} ight floor = leftlfloordfrac{1}{2}sumlimits_{i=1}^x sumlimits_{k=1}^n[b_igeq k][b_{x-i}geq k] ight floor = leftlfloordfrac{1}{2}sumlimits_{k=1}^nsumlimits_{i=1}^x [b_igeq k][b_{x-i}geq k] ight floor)。
然后就可以跑 (m) 次 NTT，时间复杂度为 (O(nmlog m))。
考虑不同的 (a) 数量不超过 (sqrt n)，所以可以离散化之后再做，时间复杂度为 (O(sqrt n mlog m))。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define MAX_N (100000 + 5)
#define MAX_M (100000 + 5)
#define G 3
#define mod 998244353
#define LL long long
using std::swap;
using std::sort;
using std::unique;
using std::lower_bound;
int n, m, N, invN, invG;
int a[MAX_M], b[MAX_N];
int f[MAX_M << 2], pos[MAX_N << 2];
int ans[MAX_M << 1];
void Read(int &x) {
	x = 0;
	char ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
}
int Pow(int x, int y) {
	int res = 1;
	for (; y; y >>= 1, x = (LL)x * x % mod) if (y & 1) res = (LL)res * x % mod;
	return res;
}
void NTT(int *f, bool is) {
	for (int i = 0; i < N; ++i) if (i < pos[i]) swap(f[i], f[pos[i]]);
	int w, cur, res;
	for (int k = 2, mid = 1; k <= N; k <<= 1, mid <<= 1) {
		if (is) w = Pow(invG, (mod - 1) / k);
		else w = Pow(G, (mod - 1) / k);
		for (int i = 0; i < N; i += k) {
			cur = 1;
			for (int j = i; j < i + mid; ++j, cur = (LL)cur * w % mod) {
				res = (LL)cur * f[j + mid] % mod;
				f[j + mid] = f[j] - res;
				if (f[j + mid] < 0) f[j + mid] += mod;
				f[j] = f[j] + res;
				if (f[j] >= mod) f[j] -= mod;
			}
		}
	}
	if (is) for (int i = 0; i < N; ++i) f[i] = (LL)f[i] * invN % mod;
}
int main() {
	Read(n), Read(m);
	int x, cnt = 0;
	for (int i = 1; i <= n; ++i) Read(x), ++a[x];
	for (int i = 1; i <= m; ++i) b[++cnt] = a[i];
	b[++cnt] = 0;
	sort(b + 1, b + cnt + 1);
	cnt = unique(b + 1, b + cnt + 1) - b - 1;
	for (int i = 1; i <= m; ++i) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
	for (N = 1; N <= m + m; N <<= 1);
	invN = Pow(N, mod - 2), invG = Pow(G, mod - 2);
	for (int i = 1; i < N; ++i) pos[i] = pos[i >> 1] >> 1 | (i & 1 ? N >> 1 : 0);
	for (int k = 2; k <= cnt; ++k) {
		memset(f, 0, sizeof f);
		for (int i = 0; i <= m; ++i) f[i] = a[i] >= k ? 1 : 0;
		NTT(f, 0);
		for (int i = 0; i < N; ++i) f[i] = (LL)f[i] * f[i] % mod;
		NTT(f, 1); 
		for (int i = 1; i <= m + m; ++i) ans[i] += f[i] * (b[k] - b[k - 1]);
	}
	for (int i = 1; i <= m + m; ++i) ans[i] >>= 1;
	int Ans = 0;
	for (int i = 1; i <= m + m; ++i) if (ans[i] > ans[Ans]) Ans = i;
	printf("%d %d", ans[Ans], Ans);
	return 0;
}

当然也可以根号分治做，个人以为没必要。