[CSP-J 2022 山东] 吟诗

知识点

状压动态规划、后缀和、补集计数

解题思路

设S=X+Y+Z。用S位掩码记录当前序列所有不超过S的非空后缀和：第v-1位表示和v存在。追加数字a时，新状态为((mask<<a)|(1<<(a-1)))&((1<<S)-1)。如果状态同时包含Z、Y+Z、S三个后缀和，就形成三个紧邻非空片段，应从“未出现”DP中排除。初态空串mask=0，迭代N次后用10^N减去全部存活状态计数。

正确性说明

所有数均为正，所以同一终点的后缀和随向左扩展严格增加。Z、Y+Z、S三个后缀和同时存在，等价于能从后往前切出和依次为Z、Y、X的三段。追加数字后的全部新后缀包括单个a和旧后缀加a，掩码转移完整；超过S的后缀永远不会再变小，可丢弃。每个字符串对应唯一状态路径，排除首次出现目标的转移后，DP恰好统计完全不含妙手的序列，取补集即为所求。

易错点

判断后缀和应使用Z、Y+Z、X+Y+Z，不是X、X+Y、总和；模数为998244353；序列元素1到10，边界S最大17。

复杂度

时间O(N·2^(X+Y+Z)·10)，空间O(2^(X+Y+Z))。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);const int MOD=998244353;int n,x,y,z;cin>>n>>x>>y>>z;int S=x+y+z,M=1<<S,need=(1<<(z-1))|(1<<(y+z-1))|(1<<(S-1));vector<int>dp(M),ndp(M);dp[0]=1;long long all=1;for(int i=0;i<n;i++){fill(ndp.begin(),ndp.end(),0);for(int s=0;s<M;s++)if(dp[s])for(int a=1;a<=10;a++){int t=((s<<a)|(1<<(a-1)))&(M-1);if((t&need)==need)continue;int v=ndp[t]+dp[s];if(v>=MOD)v-=MOD;ndp[t]=v;}dp.swap(ndp);all=all*10%MOD;}long long bad=0;for(int v:dp)bad=(bad+v)%MOD;cout<<(all-bad+MOD)%MOD<<'\n';}