[ABC358E] Alphabet Tiles

zrl123456 · 2024-06-16 11:53:50 · 题解

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

设一序列 \{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;
}