ZROI Easy Sum(生成函数，分块，dp，组合，多项式)

解题思路

首先，考虑$C_{a+b-k}^a$的组合意义，相当于是在二维平面上，从$(a,b)$走到$(0,k)$，每次可以向下或者向左走的方案数的方案数

因此，原题等价于对于$k=0\dots \dots n-1,$求所有点到$(0,k)$的方案数之和。

首先可以把坐标系水平翻转一下，这样的话就相当于每次可以向左或者向上走，水平翻转是指$(x,y)$变成$(x,n-1-y)$，这样做是为了方便卷积。

接下来,我们对x这一维分块，取一个整数B，然后设$dp[i][j]$,表示从所有点走到$(iB,j)$的方案数。
不过这样子的话会算重，于是我们换一下，设$dp[i][j]$表示从所有点走到$(iB,j)$,且最后一步向左走的方案数。

首先，考虑如果$iB$到$(i+1)B$这段区间内没有点的情况。

我们可以写出一个$dp$式子：
$$dp[i][j]=\sum _{k}dp[i+1][k]C_{j-k+B-1}^{j-k}$$减一是因为最后一步钦定了。
我们可以把它看成两个多项式卷积的形式，其中，第二个多项式为$C_{B-1}^0,C_{B-1+1}^1,C_{B-1+2}^2\dots \dots$
根据经典结论，$$C_i^0,C_{i+1}^1\dots \dots$$的OGF为$$\frac{1}{(1-x{)}^{i+1}}$$
因此该多项式的OGF为$$\frac{1}{(1-x{)}^B}$$
然后考虑新加的点，那么就会有dp式子：
$$dp[i][j]=dp[i][j]+C_{j-a+l-1}^{j-a}$$,其中l表示这个点到$x=Bi$这条直线的距离。
这种转移也可以写成生成函数:
$$x^b\frac{1}{(1-x{)}^l}$$
综合一下，设$F(i,x)=dp[i]$的生成函数.
那么$$F(i,x)=F(i-1,x)\times \frac{1}{(1-x{)}^B}+\sum _i{x}^b\frac{1}{(1-x{)}^l}$$
不过如果就是这个样子的话，那么后面的部分是$O(n^2)$的
乘法分配律：
$$F(i,x)=(F(i-1,x)+\sum _i{x}^b\frac{1}{(1-x{)}^{l-B}})\times \frac{1}{(1-x{)}^B}$$
$$F(i,x)=(F(i-1,x)+\sum _i{x}^b(1-x{)}^{B-l})\times \frac{1}{(1-x{)}^B}$$
这样做的好处是，前面加的部分只需要$O(B)$就可以计算了。
接着我们只需要展开$$(1-x{)}^{B-l},\frac{1}{(1-x{)}^B}$$然后做卷积就行了。
前面可以二项式定理展开（注意x前面是符号），后面直接套用上边的结论展开就行了。
时间复杂度$O(nB+n(n/B)logn)$,取$B=\sqrt{(}nlogn)$
最后因为我们的dp钦定最后一步向左走，因此只需要在做一遍前缀和求出最后一步向上走的方案数就行了。
别忘了因为一开始翻转了坐标系，因此最后要再翻回来。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+7;
typedef long long LL;
const int mod = 998244353;
LL Pow(LL a,LL b)
{
    LL res=1;
    while(b)
    {
        if(b&1)res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}
LL G=3,IG=Pow(3,mod-2);
#define Poly vector<LL>
#define len(x) (int)x.size()
#define turn(x,v) x.resize(v)
int tr[N*4];
void Retry(int n)
{
    for(int i=0;i<n;i++)
    tr[i]=((tr[i>>1]>>1)|((i&1)?(n>>1):0));
}
void NTT(Poly &f,int opt)
{
    int n=len(f);
    for(int i=0;i<n;i++)
    if(i<tr[i]) swap(f[i],f[tr[i]]);
    for(int len=2;len<=n;len<<=1)
    {
        int l=(len>>1);
        LL w=Pow(opt==1?G:IG,(mod-1)/len);
        for(int i=0;i<n;i+=len)
        {
            LL g=1;
            for(int j=i;j<i+l;j++)
            {
                LL v=g*f[j+l]%mod;
                f[j+l]=(f[j]-v+mod)%mod;
                f[j]=(f[j]+v)%mod;
                g=1ll*g*w%mod;
            }
        }
    }
}
Poly Mul(Poly f ,Poly g)
{
    int n=len(f),m=len(g);
    int len=1;
    for(;len<=n+m-1;len<<=1);
    Retry(len);turn(f,len);turn(g,len);
    NTT(f,1);NTT(g,1);
    for(int i=0;i<len;i++)
    f[i]=1ll*f[i]*g[i]%mod;
    NTT(f,-1);
    LL invn=Pow(len,mod-2);
    for(int i=0;i<len;i++)
    f[i]=1ll*f[i]*invn%mod;
    turn(f,n);
    return f;
}
int n;
LL fac[N],ifac[N];
void init(int x)
{
    fac[0]=1;
    for(int i=1;i<=x;i++)
    fac[i]=1ll*fac[i-1]*i%mod;
    ifac[x]=Pow(fac[x],mod-2);
    for(int i=x-1;i>=0;i--)
    ifac[i]=(LL)ifac[i+1]*(i+1)%mod;
}
LL C(int a,int b)
{
    if(a<0||b<0||a<b) return 0;
    return (LL)fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}
int a[N],b[N];
vector<int> s[N];
LL pw(int x)
{
    if(x&1) return mod-1;
    return 1;
}
int main()
{
    freopen("easysum.in","r",stdin);
    freopen("easysum.out","w",stdout);
    cin>>n;
    int mx=0;
    for(int i=1;i<=n;i++)
    scanf("%d %d",&a[i],&b[i]),mx=max(mx,a[i]),b[i]=n-1-b[i];
    init(2*n);
    mx=max(mx,1);
    int B=sqrt(mx*log2(mx));
    B=max(B,1);
    int cnt=mx/B;
    for(int i=1;i<=n;i++)
    s[(a[i]/B)].push_back(i);
    Poly F;
    turn(F,n);
    for(int k=cnt;k>=0;k--)
    {
        for(auto x:s[k])
        {
            int l=a[x]%B;
            for(int i=0;i<=B-l;i++)
            if(b[x]+i<n) F[b[x]+i]=(F[b[x]+i]+(LL)pw(i)*C(B-l,i)%mod)%mod;
        }
        Poly G;
        turn(G,n);
        for(int i=0;i<n;i++)
        G[i]=C(B+i-1,i);
        F=Mul(F,G);
    }
    for(int i=1;i<n;i++)
    F[i]=(F[i-1]+F[i])%mod;
    reverse(F.begin(),F.end());
    for(int i=0;i<n;i++)
    printf("%lld ",F[i]);
    return 0;
}
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
113
114
115
116
117
118
119
120
121
122
123
124
125