Zroi easy sum (generating function, block, DP, combination, polynomial)

Their thinking

First , consider $C_{a+b-k}^a$ The combined meaning of , Equivalent to two-dimensional plane , from $(a,b)$ Go to the $(0,k)$, The number of schemes that can go down or left each time

therefore , The original question is equivalent to $k=0\dots \dots n-1,$ Ask all points to $(0,k)$ The sum of the solutions .

First, you can flip the coordinate system horizontally , In this way, you can walk left or up every time , Horizontal flip refers to $(x,y)$ become $(x,n-1-y)$, This is done to facilitate convolution .

Next , We are right. x This one-dimensional block , Take an integer B, Then set $dp[i][j]$, It means walking from all points to $(iB,j)$ Number of alternatives .
But it will be heavy in this way , So we changed , set up $dp[i][j]$ It means walking from all points to $(iB,j)$, And the number of schemes that go left in the last step .

First , Consider if $iB$ To $(i+1)B$ There is no point in this interval .

We can write a $dp$ Formula ：
$$dp[i][j]=\sum _{k}dp[i+1][k]C_{j-k+B-1}^{j-k}$$ Minus one is because the last step was decided .
We can regard it as the convolution of two polynomials , among , The second polynomial is $C_{B-1}^0,C_{B-1+1}^1,C_{B-1+2}^2\dots \dots$
According to the classic conclusion ,$$C_i^0,C_{i+1}^1\dots \dots$$ Of OGF by $$\frac{1}{(1-x{)}^{i+1}}$$
Therefore, the polynomial OGF by $$\frac{1}{(1-x{)}^B}$$
Then consider the new points , Then there will be dp Formula ：
$$dp[i][j]=dp[i][j]+C_{j-a+l-1}^{j-a}$$, among l It means from this point to $x=Bi$ The distance of this straight line .
This transfer can also be written as a generating function :
$$x^b\frac{1}{(1-x{)}^l}$$
Take it all together , set up $F(i,x)=dp[i]$ The generating function of .
that $$F(i,x)=F(i-1,x)\times \frac{1}{(1-x{)}^B}+\sum _i{x}^b\frac{1}{(1-x{)}^l}$$
But if it's like this , Then the latter part is $O(n^2)$ Of
The law of multiplicative distribution ：
$$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}$$
The advantage of this is , The part added above only needs $O(B)$ You can calculate .
Then we just need to expand $$(1-x{)}^{B-l},\frac{1}{(1-x{)}^B}$$ Then do convolution .
The above can be expanded by binomial theorem （ Be careful x Symbol in front ）, Just apply the above conclusion directly to expand later .
Time complexity $O(nB+n(n/B)logn)$, take $B=\sqrt{(}nlogn)$
Finally, because of our dp King decided to take the last step to the left , Therefore, you only need to do the prefix once and find the number of schemes that go up in the last step .
Don't forget because you flipped the coordinate system at the beginning , So finally turn it back .

#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;
}