LG 11 月月赛 II T4

看到膜数和 $ 10^5 $ 以及 $ n^2 $ 的部分分想到很可能是 NTT 于是开始推式子

首先看到式子可以化作，

如果 $k = 0$ , $ f(l , r , k) $ 为 $ [l = r]a[l] $
否则，$ f(l , r , k) $ 为 $ \displaystyle \sum_{\forall [a,b] \sub [l,r]} f(a,b,k-1) $ 比较通俗的语言就是对于 $ [l,r] $ 的所有子区间求 $ f(a,b,k-1) $ 的和。

于是可以考虑对于每一个 $ a[i] $ 的贡献，其实就是左端点到 $ i $ 以及右端点到 $ i $ 分别选择 $ k $ 个位置，这个就是经典的隔板法了。最后的式子：

$ sum_{1, r, k}=\sum_{i=1}^{r} a_{i}\left(\begin{array}{c}{i+k-2} \ {k-1}\end{array}\right)\left(\begin{array}{c}{r-i+k-1} \ {k-1}\end{array}\right) $

然而出题人把 $ k $ 放到了 $ 998244353 $ 级别，于是只有分块打个表过去了，不知道有没有什么更优秀的处理方法了（

(代码中省略了表。。毕竟太长了)

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

using namespace std;

//#define int long long

#define MAXN 1000006

#define P 998244353

typedef long long ll;

int n , k;

int power( int a , int x ) {

    int ans = 1 , cur = a % P;

    while( x ) {

        if( x & 1 ) ans = 1ll * ans * cur % P;

        cur = 1ll * cur * cur % P , x >>= 1;

    }

    return ans;

}

int A[MAXN] , B[MAXN] , r[MAXN];

inline void NTT(int* a, int len, int type) {

    for (int i = 0; i < len; i++) if (i < r[i]) swap(a[i], a[r[i]]);

    for (int mid = 2; mid <= len; mid <<= 1) {

        int Wn = power(3, type ? (P - 1) / mid : P - 1 - (P - 1) / mid);

        for (int i = 0; i < len; i += mid)

            for (int j = i, w = 1, t; j < i + (mid >> 1); j++, w = (ll)w * Wn % P)

                t = (ll)w * a[j + (mid >> 1)] % P, a[j + (mid >> 1)] = (a[j] - t + P) % P, a[j] = (a[j] + t) % P;

    }

    if (!type) for (int inv = power(len, P - 2), i = 0; i < len; i++) a[i] = (ll)a[i] * inv % P;

}

int J[MAXN];

const int jj[] = {/* ... */};

int jk = 0;

int getJ( int x ) {

    int cur = k , res = jk;

    while( cur + 1 <= x ) ++ cur , res = 1ll * res * cur % P;

    while( cur - 1 >= x ) res = 1ll * res * power( cur , P - 2 ) % P , -- cur;

    return res;

}

signed main() {

//    freopen("input","r",stdin);

    cin >> n >> k;

    if( k == 1 ) {

        for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&A[i]) , A[i] = ( A[i] + A[i - 1] ) % P , printf("%d ",A[i]);

        return 0;

    }

    J[0] = 1; for( int i = 1 ; i < MAXN ; ++ i ) J[i] = 1ll * J[i - 1] * i % P;

    jk = jj[k / 1000000];

    for( int r = k / 1000000 * 1000000 + 1 ; r <= k ; ++ r )

        jk = 1ll * jk * r % P;

    int re = getJ( k - 2 ) , re1 = getJ( k - 1 );

//    cout << getJ( 10000000 ) << endl;

    int tm = re1;

    B[0] = re1;

    for( int i = 1 ; i <= n ; ++ i )

        scanf("%d",&A[i]) , re = 1ll * re * ( i + k - 2 ) % P , re1 = 1ll * re1 * ( i + k - 1 ) % P ,

                A[i] = 1ll * A[i] * re % P * power( J[i - 1] , P - 2 ) % P ,

                B[i] = 1ll * re1 * power( J[i] , P - 2 ) % P;

    int len = 1, l = 0;

    while (len <= n * 2) len <<= 1, l++;

    for (int i = 0; i < len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);

    NTT( A , len , 1 ) , NTT( B , len , 1 );

    for( int i = 0 ; i < len ; ++ i ) A[i] = 1ll * A[i] * B[i] % P;

    NTT( A , len , 0 );

    int x = power( 1ll * tm * tm % P , P - 2 );

    for( int i = 1 ; i <= n ; ++ i ) printf("%d ", (int) (1ll * x * A[i] % P) );

}

巴特西

LG 11 月月赛 II T4

LG 11 月月赛 II T4

最新文章

热门文章

巴特西

LG 11 月 月赛 II T4

LG 11 月 月赛 II T4

最新文章

热门文章

LG 11 月月赛 II T4

LG 11 月月赛 II T4