【GJOI 2023.10.5 T1】 雷老师的正偏态分布

雷老师的正偏态分布

题意：给出一个长度为 \(n\) 的 \(a\) 数组，其中 \(1 \le a_i \le V , 1 \le i \le n\) 。统计其中的满足平均数严格小于中位数且大小为奇数的子集数量，\(n \le 100 , V \le 800\)，时限 \(4\) s 。

输入：
5 10
1 2 7 9 10
输出：
8

首先，可以考虑排序，保证一个子集中小于的中位数的数都在中位数前面，大于中位数的在中位数后面。
那么我们就可以枚举中位数是哪个，然后统计答案。
每次枚举一个 \(k\) ，表示中位数前面有 \(k\) 个数，后面有 \(k\) 个数。
由于要求平均数小于中位数，设中位数为 \(p\) ，前面的数和为 \(x\) ，后面的数为 \(y\) ，那需满足 \(p \times k -x< y - p \times k\) 。
那就可以对前面与后面的数做两次背包，分别统计有 \(k\) 个数和为 \(x\) 有多少种方案即可，最后左右统计，累加答案，时间复杂度 \(O(n^5 V)\) 。
将其优化，考虑到每次求的背包都是一段从 \(1\) 或 \(n\) 开始的数，可以每次将一个数加进背包里，
对于从 \(n\) 开始的数，先预处理出 \(1\) ~ \(n\) 情况，然后用反悔背包，每次将一个数从背包中删去即可，步骤与加进去相反。
然后做的同时统计答案即可。
时间复杂度 \(O(n^3V)\) ，再略微卡卡常即可。

code

#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const int mod=998244353;
int n,m,a[105],f2[105][80005],f1[105][80005],t[80005],V,s=0;
int main()
{
	scanf("%d%d",&n,&m);
	V=n*m;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	f1[0][0]=f2[0][0]=1;
	for(register int i=2;i<=n;i++)
	{
		for(register int j=n;j>=1;j--)
		{
			for(register int u=V;u>=a[i];u--)
			{
				f2[j][u]=f2[j-1][u-a[i]]+f2[j][u];
				f2[j][u]=f2[j][u]>mod?f2[j][u]-mod:f2[j][u];
			}
		}
	}
	int q,op,w=0;
	for(register int i=2;i<n;i++)
	{
		for(register int j=n;j>=1;j--)
		{
			for(register int u=V;u>=a[i-1];u--)
			{
				f1[j][u]=(f1[j-1][u-a[i-1]]+f1[j][u]);
				f1[j][u]=f1[j][u]>mod?f1[j][u]-mod:f1[j][u];
			}
		}
		for(register int j=1;j<=n;j++)
		{
			for(register int u=a[i];u<=V;u++)
			{
				f2[j][u]=(f2[j][u]-f2[j-1][u-a[i]]+mod);
				f2[j][u]=f2[j][u]>mod?f2[j][u]-mod:f2[j][u];
			}
		}
		for(register int j=1;j<=n;j++)
		{
			w=0;
			op=a[i]*j+1;
			for(register int u=1;u<=op;u++)
			{
				w+=f1[j][u-1];
				w=w>mod?w-mod:w;
				q=a[i]*j-u+a[i]*j;
				if(q<=0)break;
				s=(s+(int)(f2[j][q]*(long long)(w)%mod))%mod;
				s%=mod;
			}
		}
	}
	cout<<s;
	








  return 0;
}