题目

题目描述

雨打在窗沿，下坠，一级一级。

这里一共有 n 级窗沿，从高到低编号，最高层编号为 1，最底层编号为 n。假设在某一瞬间，第 i 级窗沿上有 a_i 单位体积的雨水。由于奇妙的物理原因，第 i 级的雨水将在下一个瞬间滴向第 i+1,i+2,\dots,\min\{i+k,n\} 级，也可能留在第 i 级，但是每一种去向的雨水的单位体积都应是非负整数，且总和为 a_i。

设在「下一个瞬间」，第 i 级窗沿上有 a_i' 单位的雨水，那么称此时雨水的奇妙度为 \prod_{i=1}^n a_i'。现在，悲伤的人儿想知道，对于所有本质不同的「下一个瞬间」，雨水的奇妙度之和对素数 P=998244353 取模的结果。

两个「下一个瞬间」本质不同，当且仅当存在编号 i<j 的两级窗沿，从窗沿 i 滴向窗沿 j 的雨水的单位体积不同。

数据范围

对于 100\% 的数据，满足 0\le k<n\le 32,0\le a_i<P。

分析

Subtask 1,2,3

想必就不用我多说了吧

Subtask 4

可以直接搜索每个窗沿到其它窗沿的雨滴数量。

复杂度看实现，不过肯定是能过的。

Subtask 5

这个部分分还是蛮重要的。

我们考虑将题目提到的方法扩展一下。设 c_k 为窗沿 k 滴到窗沿 k+1 的雨滴数，为了方便我们也同样定义 c_0=c_n=0。不难发现答案的式子如下：

\sum_{\{c\}}\prod_{k=1}^n(a_k-c_k+c_{k-1})

考虑直接拆开和式。我们形式地写为：

\sum_{\{c\}}\sum_{S}[S\subseteq\{1,2,3,\dots,n\}] \prod_{k\in S}(a_k-c_k)\prod_{k\not\in S} c_{k-1}

我们可以尝试将同一下标的 c 合在一起写，这样我们就可以收起外层 \sum_{\{c\}}，使得贡献独立。举个例子，当 k<n 时，我们考虑 k,k+1 的存在情况：

不难发现此时某一个 k 的贡献仅仅和 k-1 是否在 S 中相关，因此设计一个 f_{i,0/1} 进行转移即可。

时间复杂度为 O(n)。

Subtask 6

类似于 Subtask 5 的处理，设 c_{i,j} 为窗沿 i 滴到窗沿 i+j 的雨滴数；特别地，认为 c_{i,0} 表示窗沿 i 留下未滴落的雨滴数量。同样为了方便，我们认为 i+j>n 的时候 c_{i,j}=0。因此有如下和式：

\sum_{\{c\}}\prod_{i=1}^{n}\left(\sum_{j=0}^{\min\{i-1,k\}}c_{i-j,j}\right)

同样的处理方法，我们把外层 \prod 展开，得到若干个 n 次单项式的和；再处理单个的 n 次单项式，从而将 \sum_{\{c\}} 利用乘法分配律收拢，加速运算。

不妨考虑这样一个 n 次单项式：设 S_i 为式子中 c_{i,*} 的出现下标，也即，这个乘积式为：

\prod_{i=1}^n\prod_{j\in S_i}c_{i,j}

那么，考虑外层 \sum_{\{c\}} 的影响。由于 c 的限制为 \forall 1\le i\le n,\sum_jc_{i,j}=a_i，所以第一维不同的 c 之间互不影响。利用乘法分配律，我们可以将和式写成：

\prod_{i=1}^n\sum_{\{c_i\}}\left[\sum_{j}c_{i,j}=a_i\right]\prod_{j\in S_i}c_{i,j}

接下来，尝试收拢内层的和式套乘积式。不妨设 r_i 表示 c_{i,*} 中有 r_i 个变量可以取到非 0 的值，也即 r_i=\min\{n-i,k\}+1。则，我们可以构造组合意义：

有 r_i 个盒子，编号为 0,1,2,\dots,r_i-1。其中编号落在 S_i 中的盒子，放了 x 个球会贡献 x；而其它盒子无论放多少个球，贡献都是 1。一种方案的贡献为各个盒子的贡献的积。求往 r_i 个盒子中任意放 a_i 个没有区别的球的贡献之和。

事实上，我们发现答案和 S_i 没有关系，而只和 |S_i| 有关。另一方面，我们容易构造出生成函数来描述这个问题：编号在 S_i 中的盒子，生成函数为 \frac{x}{(1-x)^2}；剩下的盒子，生成函数为 \frac{1}{1-x}。如果令 |S_i|=s_i，则可以得到后面的和式结果为：

[x^{a_i}]\left(\frac{x}{(1-x)^2}\right)^{s_i}\frac{1}{(1-x)^{r_i-s_i}}=\binom{a_i+r_i-1}{s_i+r_i-1}

再来看如何将巨大的乘积式拆分成若干个单项式。由于答案计算的过程中，只有 s_i 会受到拆分方式的影响，因此我们考虑 s_i 是怎么来的：乘积中，每个 i 向 \max\{i-k,1\}\le j\le i 中的恰好一个 j 贡献 s_j。反过来，每个 i 的 s_i 可以从 i,i+1,i+2,\dots,i+r_i-1 这些位置中取，且一个位置不能贡献两次 s。以下，如果一个位置已经贡献过一次 s，我们就称它为被占用。

所以，现在可以解决 Subtask 6。此时每个 i 的指数可以由 i,i+1,i+2,\dots,n 贡献到，因此只需要设计 f_{i,j} 表示后缀 i 中还剩 j 个位置未被占用的权值和。转移只需要枚举一下 s，用组合数计算即可。

时间复杂度可以做到 O(n^3)。

Subtask 7

进一步拓展 Subtask 6 中的处理方法，我们压一个状态 f_{i,S}，用 i 表示当前后缀，用 S 表示 i,i+1,i+2,\dots,\min\{i+k,n\} 各自是否被占用。

如果实现不恰当，复杂度会到 O(n3^k)，无法通过这个子任务。但是注意到 i 的贡献只和 S 中新增的被占用位置个数有关，并且能贡献到 S 的前驱状态 T 得满足 T\subseteq S，因此我们可以直接做高维前缀和，同时记录一下新增个数即可。

时间复杂度可以做到 O(nk^22^k)。

这个部分分还可以进行容斥。我们要求所有的位置最终必须被占用，对被占用时是否在有效的 [i,i+k] 范围内进行容斥。则设状态 f_{i,S,j}，用 S 表示钦定了 [i,i+k] 中哪些位置必须超出限制，用 j 表示可选（包括没有被限制和钦定超出限制占用且已经超出限制的位置）但尚未被占用的位置个数。转移可以做到 O(n^32^k)。

Subtask 8

此时直接莽 O(nk^22^k) 肯定不行。注意当 k 比较大的时候，只有较少的位置有可能会超出限制，因此我们可以在 k 和 k+1 中间切一刀，分成前后两段。我们可以尝试枚举后半段位置是否被前半段占用，前后贡献就分开了。并且，前后内部贡献不存在超出限制的情况，我们可以直接看作是“内部的一个后缀都可以贡献”，因而直接转化到了 Subtask 6 的情况。

实现时，可以设状态 f_{i,j,S}，用 i 标识后缀，用 j 表示 [i,k] 中有多少位置尚未被占用，用 S 表示 (k,n] 中位置的占用情况。转移相当于同时对 j 做 Subtask 6、对 S 做 Subtask 7 的转移，可以做到 O(nk^32^{n-k})。而后半部分的内部贡献可以枚举 S，并做一个类似于 Subtask 6 的转移（只需注意不要将钦定被前半段占用的位置加入）即可做到 O(nk^22^{n-k})。

两侧平衡一下复杂度，理论上总的时间复杂度最小可以为 O(nk^{2.5}2^{\frac n 2})。但是，考虑到 k 是整数，因此很难取到这个最优结果。

Subtask 9

其实想到了容斥方法基本就解决本题了。

同样考虑的是，k 较大的时候较少的位置才有可能超出限制。因此，我们对于 (k+1,n] 中的位置，枚举它们是否被超出限制占用。剩下的，可以用 f_{i,j} 表示后缀 i 中有 j 个可选但未被占用的位置。从 f_{i+1} 过来时，需要同时考虑 i 是否被加入和 i+k+1 是否被加入；话虽如此，转移本身仍然类似于 Subtask 6，复杂度可以做到 O(n^2k2^{n-k})。

结合 Subtask 7 的算法和 Subtask 9 的算法即可得到 O(nk^22^{\frac n 2}) 的算法。

代码

#include <cstdio>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int mod = 998244353;
const int MAXN = 100;

template<typename _T>
void read( _T &x ) {
    x = 0; char s = getchar(); bool f = false;
    while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
    while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}

template<typename _T>
void write( _T x ) {
    if( x < 0 ) putchar( '-' ), x = -x;
    if( 9 < x ) write( x / 10 );
    putchar( x % 10 + '0' );
}

template<typename _T>
_T MIN( const _T a, const _T b ) {
    return a < b ? a : b;
}

int C[MAXN][MAXN];

int A[MAXN], coe[MAXN][MAXN];
int inv[MAXN];

int N, K;

inline int Qkpow( int, int );
inline int Mul( int x, int v ) { return 1ll * x * v % mod; }
inline int Inv( const int a ) { return Qkpow( a, mod - 2 ); }
inline int Sub( int x, int v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, int v ) { return ( x += v ) >= mod ? x - mod : x; }

inline int Qkpow( int base, int indx ) {
    int ret = 1;
    while( indx ) {
        if( indx & 1 ) ret = Mul( ret, base );
        base = Mul( base, base ), indx >>= 1;
    }
    return ret;
}

void Init( const int k ) {
    inv[1] = 1; rep( i, 2, k << 1 ) inv[i] = Mul( inv[mod % i], mod - mod / i );
    rep( i, 0, k ) {
        C[i][0] = C[i][i] = 1;
        rep( j, 1, i - 1 ) C[i][j] = Add( C[i - 1][j], C[i - 1][j - 1] );
    }
}

int Binom( const int x, const int r ) {
    if( x < r ) { return 0; } int ret = 1;
    rep( i, 1, r ) ret = Mul( ret, Mul( ( x - i + 1 ) % mod, inv[i] ) );
    return ret;
}

int Query( const int j, const int k, const int n ) {
    if( n < k ) return 0;
    return Binom( n + j - 1, j + k - 1 );
}

namespace SmallK {
    const int MAXS = ( 1 << 16 ) + 5;

    int f[MAXS], g[MAXS][MAXN];

    void Solve() {
        if( K == 0 ) {
            int ans = 1;
            rep( i, 1, N ) ans = Mul( ans, A[i] );
            write( ans ), putchar( '\n' );
            return ;
        }

        f[0] = coe[N][0], f[1] = coe[N][1];
        per( i, N - 1, 1 ) {
            int lim = MIN( N - i + 1, K + 1 );
            rep( j, 0, ( 1 << lim ) - 1 ) rep( k, 0, lim ) g[j][k] = 0;
            rep( j, 0, ( 1 << ( lim - 1 ) ) - 1 ) g[j][0] = f[j], f[j] = 0;
            rep( j, 0, lim - 1 ) 
                per( k, ( 1 << lim ) - 1, 0 )
                    if( ! ( k >> j & 1 ) ) per( t, lim - 1, 0 )
                        g[k | ( 1 << j )][t + 1] = Add( g[k | ( 1 << j )][t + 1], g[k][t] );
            if( i <= N - K ) {
                rep( k, 0, ( 1 << lim ) - 1 )
                    if( k & 1 ) rep( t, 0, lim )
                        f[k >> 1] = Add( f[k >> 1], Mul( g[k][t], coe[i][t] ) );
            } else {
                rep( k, 0, ( 1 << lim ) - 1 )
                    rep( t, 0, lim ) f[k] = Add( f[k], Mul( g[k][t], coe[i][t] ) );
            }
        }
        write( f[( 1 << K ) - 1] ), putchar( '\n' );
    }
}

namespace LargeK {
    int f[MAXN];

    void Solve() {
        int rest = N - K - 1, ans = 0, lim, tmp, shft = 0;
        for( unsigned S = 0 ; S < ( 1u << rest ) ; S ++ ) {
            f[0] = 1, lim = 0;
            per( i, N, 1 ) {
                shft = 0;
                if( i > K + 1 ) shft += ! ( S >> ( i - K - 2 ) & 1 );
                else shft ++;
                if( i + K < N ) shft += S >> ( i - 1 ) & 1;

                if( shft ) {
                    per( j, lim, 0 ) f[j + shft] = f[j];
                    rep( j, 0, shft - 1 ) f[j] = 0;
                    lim += shft;
                }

                rep( j, 0, lim ) {
                    tmp = 0;
                    for( int t = 0 ; t <= K + 1 && t + j <= lim ; t ++ )
                        tmp = Add( tmp, Mul( f[j + t], Mul( C[j + t][t], coe[i][t] ) ) );
                    f[j] = tmp;
                }
            }
            ans = __builtin_popcount( S ) & 1 ? Sub( ans, f[0] ) : Add( ans, f[0] );
        }
        write( ans ), putchar( '\n' );
    }
}

int main() {
    read( N ), read( K );
    Init( K + 1 );
    rep( i, 1, N ) {
        read( A[i] );
        int lim = MIN( N - i + 1, K + 1 );
        rep( j, 0, lim ) coe[i][j] = Query( lim, j, A[i] );
    }
    if( K < N / 2 )
        SmallK :: Solve();
    else
        LargeK :: Solve();
    return 0;
}