1.子集

题意

思路

依然计数题起手。

先考虑 $k=0$ 的情况。设 $f_{i,j}$ 表示，前 $i$ 个数选出和为 $j$ 的方案数。我们发现这个和 $j$ 可能会很大，又因为这一题给出了只要 $\ge m$ 就是合法的条件。因此将所有和 $\ge m$ 的都并入 $f_{i,m}$ 去。

因此有转移：
$$f_{i,\min (j+a_i,m)}\leftarrow f_{i-1,j}$$

相当于新增选择 $a_i$ 的贡献。因为 $f_{i,j}$ 不一定选 $a_i$，因此还要合并前面的贡献 $f_{i,j}\leftarrow f_{i-1,j},j\in [0,m]$。同时记得初始化 $f_{0,0}=1$。

f[0][0]=1;
for(int i=1;i<=n;i++)
{
	for(int j=0;j<=m;j++)
	f[i][j]=f[i-1][j];
	for(int j=0;j<=m;j++)
	{
		ll sum=min(j+a[i],m);
		f[i][sum]=(f[i][sum]+f[i-1][j])%mod;
	}
}
printf("%lld ",f[n][m]);//k=0

怎么推广到 $k=1\sim n$ 呢？我们考虑每一个已经合法了的子集 $f_{i,m}$，前 $i$ 个数子集和 $\ge m$ 的方案数，这些子集就是合法的 $T$。我们考虑在后面 $n-i$ 个数，选择 $k$ 个加进 $T$ 成为 $S$，此时就可以合并每个 $k$ 的答案。

为了不算重，我们每次计算，选 $a_i$ 所新增的子集（方案数为 $f_{i,m}-f_{i-1,m}$），加上 $n-i$ 个数中选的 $k$ 个，对 $an{s}_k$ 带来的贡献。

$$an{s}_k\leftarrow (f_{i,m}-f_{i-1,m})\times \left(\genfrac{}{}{0ex}{}{n-i}{k}\right)$$

这样做是正确的有一个大前提：要按照从大到小的顺序合并 $a_i$。

如果从小到大合并，对于前 $i$ 个数组成的某个子集 $T^{\prime }$，相当于加上后面 $n-i$ 个中任意一个比所有子集元素都大的数，变成 $S^{\prime }$；而这个元素替换掉 $T^{\prime }$ 中任意一个元素的新子集都是合法的，新子集的贡献不会被算上呢。

（感觉有点乱呢）

相反的，从大到小合并 $a_i$ 可以算全。

记得开 long long 和勤取模。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=3002,mod=998244353;
ll n,m;
ll a[N];
ll f[N][N];
bool cmp(ll x,ll y)
{
	return x>y;
}
ll ans[N];
ll C[N][N];
void init()
{
	for(int i=1;i<N;i++)
	C[i][0]=C[i][i]=1;
	for(int i=1;i<N;i++)
	for(int j=1;j<i;j++)
	C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
int main()
{
	freopen("subset.in","r",stdin);
	freopen("subset.out","w",stdout);
	init();
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	sort(a+1,a+n+1,cmp);
	f[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		f[i][j]=f[i-1][j];
		for(int j=0;j<=m;j++)
		{
			ll sum=min(j+a[i],m);
			f[i][sum]=(f[i][sum]+f[i-1][j])%mod;
		}
		for(int k=0;k<=n-i;k++)
		ans[k]=(ans[k]+(f[i][m]-f[i-1][m]+mod)%mod*C[n-i][k]%mod)%mod;
	}
	printf("%lld ",f[n][m]);
	for(int k=1;k<=n;k++)
	printf("%lld ",ans[k]);
	return 0;
}

2.彷徨

题意

$n\le 7.5\times 10^4$，$n-1\le m\le 2n$。

3.洛谷 P10681 COTS2024 奇偶矩阵

题意

思路

行和、列和要么是 $1$ 要么是 $2$，但我们不知道那些行的和为 $1/2$ 怎么办？那就直接枚举。

考虑枚举 $n$ 行中 $a$ 个和为 $1$ 的、$b$ 个和为 $2$ 的，$m$ 行中 $c$ 个和为 $1$ 的、$d$ 个和为 $2$ 的。

因为矩阵上能填的数只有 $0/1$，那么 $1$ 的个数就是 $a+2b=c+2d$，又因为 $a+b=n,c+d=m$，因此只需要枚举一个 $a$ 就能推出 $b,c,d$。

这时候我们可以转化题意：有 $m$ 种球，其中 $c$ 种各有 $1$ 个，$d$ 种各有 $2$ 个。有 $n$ 个桶，其中 $a$ 个容量为 $1$，$b$ 个容量为 $2$。问有多少种放球方式，满足每个桶都放满，且一个桶里不能放两个同一种球。

先不考虑两个同种球放在同一个桶里面。那就先选桶和球：$\left(\genfrac{}{}{0ex}{}{n}{a}\right)\left(\genfrac{}{}{0ex}{}{m}{c}\right)$，然后将 $c+2d$ 个球乱排放进 $a+2b$ 的空间：$(c+2d)!$。但是球的放置和桶里面球的进入，是没有顺序差别的，因此要进行神秘的去重.

因为 $b$ 个容量为 $2$ 的桶不区分放置顺序，相当于 $b$ 行上放的 $2$ 个不分左右，于是每个 $b$ 行 $÷2$，合起来就是 $÷2^b$；同样 $d$ 种各有 $2$ 个的球也没有放置先后，就要 $÷2^d$。因此要 $÷2^b÷2^d$ 去重。

接下来考虑会放重的情况，考虑容斥。钦定 $k\in [0,\min (b,d)]$ 个同种的 $2$ 个球都放在容量为 $2$ 的桶里面（不合法情况）。于是就钦定了 $2k$ 个球的放置，剩下 $c+2d-2k$ 个球随便放，去重就 $÷2^{d-k}$。同样的对于桶进入顺序的去重也是 $÷2^b$。

$$\left(\genfrac{}{}{0ex}{}{n}{a}\right)\left(\genfrac{}{}{0ex}{}{m}{c}\right)\sum _{k=0}^{\min (b,d)}(-1{)}^k(\genfrac{}{}{0ex}{}{b}{k}\left)\right(\genfrac{}{}{0ex}{}{d}{k})k!(c+2d-2k)!÷2^b÷2^{d-k}$$

注意勤取模，计算 $2$ 的幂的逆元不要漏算 $0,1$ 的。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=3002,M=6002,mod=1e9+7;
ll n,m;
ll fac[M],inv[M],ip2[M];
ll qpow(ll x,ll k)
{
	ll ret=1;
	while(k)
	{
		if(k&1)ret=ret*x%mod;
		x=x*x%mod;
		k>>=1;
	}
	return ret;
}
void init()
{
	fac[0]=1;
	for(int i=1;i<M;i++)
	fac[i]=fac[i-1]*i%mod;
	inv[M-1]=qpow(fac[M-1],mod-2);
	for(int i=M-2;i>=0;i--)
	inv[i]=inv[i+1]*(i+1)%mod;
	ip2[0]=1;
	ip2[1]=qpow(2,mod-2);
	for(int i=2;i<M;i++)
	ip2[i]=ip2[i-1]*ip2[1]%mod;
}
ll C(ll n,ll m)
{
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
ll ans;
int main()
{
	freopen("mat.in","r",stdin);
	freopen("mat.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	init();
	for(int a=0;a<=n;a++)
	{
		ll b=n-a,d=n+b-m,c=m-d;
		if(a<0||b<0||c<0||d<0)continue;
		ll ret=0;
		for(int k=0;k<=min(b,d);k++)
		{
			ll op=(k&1?-1:1);
			ans=(ans+op*C(n,a)%mod*C(m,c)%mod*
						C(b,k)%mod*C(d,k)%mod*
						fac[k]%mod*fac[c+2*d-2*k]%mod*ip2[b+d-k]%mod+mod)%mod;
		//	cout<<(k&1?-1:1)<<":"<<C(b,k)<<" "<<C(d,k)<<" "<<fac[k]<<" "<<fac[c+2*d-2*k]<<" "<<ip2[b+d-k]<<endl;
		//	cout<<b+d-k<<" inv_2: "<<ip2[b+d-k]<<"\n";
		}
	}
	printf("%lld",ans);
	return 0;
}

4.洛谷 P11945 KTSC 2025 军事基地 / safezone