本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-16 11:53:50

[ABC358E] Alphabet Tiles

题目考察：组合数学，动态规划。
题目简述：
给你一个数 $k$ 和一个序列 $\{c_{26}\}$，求满足以下条件的字符串的个数对 $998244353$ 取模的结果：

• $1\le |s|\le k$。
• 设一序列 $\{p_{26}\}$ 的 $p_i$ 为在大写字母中第 $i$ 组字母，如 $p_1$ 为 A，$p_5$ 为 E 等，则 $\displaystyle \forall i\in[1,26],\sum_{j=1}^{|s|}[s_j=p_i]\le c_i$。
  数据范围：
• $1\le k\le 10^3$
• $\forall i\in[1,26],0\le c_i\le 10^3$

我们设 $m=26$，则若直接暴力枚举，则复杂度为 $\Theta(m^k)$，根本无法接受。

考虑 dp。
我们设 $f_{i,j}$（$\displaystyle 1\le i\le 26,1\le j\le \min(k,\sum_{s=1}^{26}c_s)$）为在前 $i$ 组字母中选出 $j$ 个字母组成字符串的方案数对 $998244353$ 取模的结果，他可以由 $f_{i-1,l}$（$\max(0,j-c_i)\le l\le j$）转移而来，但是是如何转移的呢？
我们的这个长度为 $j$ 的字符串 $s$ 的第 $x$ 位（$1\le x\le j$）可以分配给前 $i-1$ 组字母其中的一组，也可以分配给第 $i$ 组，由于必须分配给前 $i-1$ 组字母 $l$ 位，则分配的方式有 $\displaystyle\binom{j}{l}$ 种，由于前 $i-1$ 组字母还可以有 $f_{i-1,l}$ 种排列，那么我们就得到了状态转移方程：
$$f_{i,j}=\sum_{l=j-c_i}^jf_{i-1,l}\times\binom{j}{l}$$ 我们可以先预处理 $\displaystyle\binom{i}{j}$（$0\le i\le k,0\le j\le i$）： $$\binom{i}{j}=\binom{i-1}{j}+\binom{i-1}{j-1}$$ 再进行 dp。

由于 $f_{i,j}$ 只与 $f_{i-1,l}$ 有关，所以我们可以将第一维压掉。

总体复杂度为 $\Theta(mk^2)$，$mk^2\le 2.6\times 10^7$，可以接受。

代码：

#include<bits\/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=y;++i) 
#define per(i,x,y) for(reg int i=x;i>=y;--i)
#define endl '\n'
#define INF 1e16
#define pb push_back
#define fi first
#define se second
#define lcm(x,y) x\/__gcd(x,y)*y
#define ull unsigned long long
using namespace std;
const int N=1005,M=35,MOD=998244353;
int c[M],f[N],dp[N][N];
signed main(){
	fst;
	reg int n,ans=0,ret=0;
	cin>>n;
	rep(i,1,26){
		cin>>c[i];
		ret+=c[i];
	}
	n=min(n,ret);
	f[0]=dp[1][1]=1;
	rep(i,2,n+1)
		rep(j,1,i) dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%MOD;
	rep(i,1,26)
		per(j,n,1)
			rep(k,max(0ll,j-c[i]),j-1) (f[j]+=f[k]*dp[j+1][k+1]%MOD)%=MOD;
	rep(i,1,n) (ans+=f[i])%=MOD;
	cout<<ans;
	return 0;
}