「Luogu P4091」[HEOI2016/TJOI2016]求和

发表于 |
字数统计: 918 | 阅读时长 ≈ 5

给定整数$n$，求$\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{i}S(i,j)\times 2^j\times j!\bmod{998244353}$，其中$S(i,j)$为第二类$\texttt{Stirling}$数。

$\texttt{Data Range:}n\leq 10^5$

链接

之前的题目好多都没放链接，之后再补qwq。

Luogu P4091

BZOJ 4555

题解

这么一长串式子看起来挺不爽，所以可以考虑推公式。

根据当$n<m$时$S(n,m)=0$，考虑将$j$的范围改一下

换个枚举顺序，再把$2^j\times j$提出来

把$\texttt{Stirling}$数展开

这个组合数看起来极其不好，展开一下，顺便把$j!$消掉

交换一下$k$和$i$的枚举顺序，把与$i$无关的提出来

把$j-k$提进去，顺便用等比数列求和消掉关与$i$的枚举

设$f_i=\frac{(-1)^i}{i!},g_i=\frac{i^{n+1}-1}{i!(i-1)}$，那么就会有

发现右边是一个卷积，使用$\texttt{NTT}$计算即可，时间复杂度$O(n\log n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=3e5+51,MOD=998244353,G=3,INVG=332748118;
ll fd,ccnt,limit,rres;
ll f[MAXN],g[MAXN],res[MAXN],rev[MAXN],inv[MAXN],fact[MAXN],finv[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline ll qpow(ll base,ll exponent)
{
    li res=1;
    while(exponent)
    {
        if(exponent&1)
        {
            res=(li)res*base%MOD;
        }
        base=(li)base*base%MOD,exponent>>=1;
    }
    return res;
}
inline void setup(ll ccnt)
{
    fact[0]=fact[1]=finv[0]=finv[1]=inv[1]=1;
    for(register int i=2;i<=ccnt;i++)
    {
        fact[i]=(li)fact[i-1]*i%MOD;
        inv[i]=(li)inv[MOD%i]*(MOD-MOD/i)%MOD;
        finv[i]=(li)finv[i-1]*inv[i]%MOD;
    }
}
inline void NTT(ll *cp,ll cnt,ll inv)
{
    ll cur=0,res=0,omg=0;
    for(register int i=0;i<cnt;i++)
    {
        if(i<rev[i])
        {
            swap(cp[i],cp[rev[i]]);
        }
    }
    for(register int i=2;i<=cnt;i<<=1)
    {
        cur=i>>1,res=qpow(inv==1?G:INVG,(MOD-1)/i);
        for(register ll *p=cp;p!=cp+cnt;p+=i)
        {
            omg=1;
            for(register int j=0;j<cur;j++)
            {
                ll t=(li)omg*p[j+cur]%MOD,t2=p[j];
                p[j+cur]=(t2-t+MOD)%MOD,p[j]=(t2+t)%MOD;
                omg=(li)omg*res%MOD;
            }
        }
    }
    if(inv==-1)
    {
        ll invl=qpow(cnt,MOD-2);
        for(register int i=0;i<=cnt;i++)
        {
            cp[i]=(li)cp[i]*invl%MOD;
        }
    }
}
int main()
{
    fd=read(),ccnt=1,limit=-1;
    while(ccnt<(fd<<1))
    {
        ccnt<<=1,limit++;
    }
    setup(ccnt);
    for(register int i=0;i<=fd;i++)
    {
        f[i]=i&1?MOD-finv[i]:finv[i];
        g[i]=i==0?1:(i==1?fd+1:(li)(qpow(i,fd+1)-1)*inv[i-1]%MOD*finv[i]%MOD);
    }
    for(register int i=0;i<ccnt;i++)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<limit);
    }
    NTT(f,ccnt,1),NTT(g,ccnt,1);
    for(register int i=0;i<=ccnt;i++)
    {
        res[i]=(li)f[i]*g[i]%MOD;
    }
    NTT(res,ccnt,-1);
    for(register int i=0;i<=fd;i++)
    {
        rres=(rres+(li)qpow(2,i)*fact[i]%MOD*res[i]%MOD)%MOD;
    }
    printf("%d",rres);
}