题解：P11856 [CSP-J2022 山东] 吟诗

· · 题解

Blog

“存在妙手”这个限制不好计数，因为可能会重复计一个妙手，且总方案数与不含妙手的方案数统计是较为容易的，所以考虑容斥，统计不含妙手的方案数。

考虑怎么刻画“分段和”的限制，显然我们可以利用前缀和的思想，如果到了第 i 位，前缀和为 s，那么只要 s-z,s-z-y,s-z-y-x 曾出现于前缀和数组中就能产生妙手。注意到 X+Y+Z\le 17，所以 s-z-y-x 与 s 的差最多只有 17，要判断存不存在，显然可以考虑把它压成一个二进制数。

因为前缀和只能利用差值来设计 DP 方案，不太直观，所以考虑转化为后缀和设计 DP：dp_{i,j} 表示考虑到第 i 位，此时后缀和存在性的状态为 j 时的方案数，避开会形成妙手的状态进行刷表法转移即可。当新加的一位数为 v 的时候，相当于 j 右移 v 位，并在二进制下的第 v 位变成 1，然后大于等于 2^{18} 的部分可以直接丢掉（用按位与实现）。

总方案数为 10^n，减掉不含妙手的方案数即为答案。

时间复杂度 O(nV2^{X+Y+Z})。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi=pair<int,int>;
const int ALL=(1<<18)-1;
const ll mod=998244353;
ll n,x,y,z,dp[50][300005],ban,ans=1;
int main()
{
    //freopen("sample.in","r",stdin);
    //freopen("sample.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>x>>y>>z;
    ban=((1<<z)|(1<<(y+z))|(1<<(x+y+z)));
    dp[0][0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=ALL;j++)
        {
            for(int v=1;v<=10;v++)
            {
                int st=(((j<<v)|(1ll<<v))&ALL);
                if((st&ban)==ban)continue;
                dp[i+1][st]=(dp[i+1][st]+dp[i][j])%mod;
            }
        }
        ans=(ans*10)%mod;
    }
    for(int i=0;i<=ALL;i++)
        ans=((ans-dp[n][i]+mod)%mod+mod)%mod;
    cout<<ans;
    return 0;
}