Comet OJ - Contest #11 E ffort（组合计数+多项式快速幂）

传送门.

题解：

考虑若最后的总伤害数是s，那么就挡板分配一下，方案数是(C_{s-1}^{n-1})。

那么问题在于总伤害数很大，不能一个一个的算。

(C_{s-1}^{n-1})的OGF是({x^{n-1}over (1-x)^n})

由(F=FA+R->F={R over 1-A})

得到递推式(A=1-(1-x)^n)，前面的项可以用组合数算出。

那么每次就是常系数齐次递推，每次搞的时候取模就好了。

复杂度是(O(log^2))

题解给出了更加巧妙的方法，我们不直接求(s)伤害的方案数。

考虑(f(x))表示任意伤害下， 分配给x个人的方案数。

当合并(f、g)两堆伤害时时，由于中间可以攃挡板，可以不插，所以就是(f*g*(1+x))。

用NTT卷积，每次算完后只用保留前n项。

直接套快速幂是(O(log^2))的，但是可以用exp优化。

初值利用这个式子就好了(sum_{i=y}^xC_{i}^y=C_{x+1}^{y+1})。

直到现在我才意识到杨辉三角的一条对角线和一列的求法是一样的，由于翻转一下就好了。

Code:

#include<bits/stdc++.h>
#define fo(i,x,y) for(int i = x,B = y; i <= B; i ++)
#define ff(i,B = y; i <  B; i ++)
#define fd(i,B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("n")
using namespace std;

const int mo = 998244353;

ll ksm(ll x,ll y) {
    ll s = 1;
    for(; y; y /= 2,x = x * x % mo)
        if(y & 1) s = s * x % mo;
    return s;
}

typedef vector<ll> V;
#define pb push_back
#define si size()
#define re resize

namespace ntt {
    const int nm = 262144;
    ll w[nm],a[nm],b[nm]; int r[nm];
    void build() {
        for(int i = 1; i < nm; i *= 2) {
            w[i] = 1;
            ll v = ksm(3,(mo - 1) / 2 / i);
            ff(j,1,i) w[i + j] = w[i + j - 1] * v % mo;
        }
    }
    void dft(ll *a,int n,int f) {
        ff(i,n) {
            r[i] = r[i / 2] / 2 + (i & 1) * (n / 2);
            if(i < r[i]) swap(a[i],a[r[i]]);
        } ll b;
        for(int i = 1; i < n; i *= 2) for(int j = 0; j < n; j += 2 * i) ff(k,i)
            b = a[i + j + k] * w[i + k],a[i + j + k] = (a[j + k] - b) % mo,a[j + k] = (a[j + k] + b) % mo;
        if(f == -1) {
            reverse(a + 1,a + n);
            b = ksm(n,mo - 2);
            ff(i,n) a[i] = (a[i] + mo) * b % mo;
        }
    }
    V operator * (V p,V q) {
        int n0 = p.si + q.si - 1,n = 1;
        while(n < n0) n *= 2;
        ff(i,n) a[i] = b[i] = 0;
        ff(i,p.si) a[i] = p[i];
        ff(i,q.si) b[i] = q[i];
        dft(a,n,1); dft(b,1);
        ff(i,n) a[i] = a[i] * b[i] % mo;
        dft(a,-1);
        p.re(n0);
        ff(i,n0) p[i] = a[i];
        return p;
    }
    void dft(V &p,int f) {
        int n = p.si;
        ff(i,n) a[i] = p[i];
        dft(a,f);
        ff(i,n) p[i] = a[i];
    }
}

using ntt :: operator *;
using ntt :: dft;

V qni(V a) {
    V b; b.re(1); b[0] = ksm(a[0],mo - 2);
    for(int n = 2; n < a.si * 2; n *= 2) {
        V c = a; c.re(n); c.re(2 * n); dft(c,1);
        b.re(2 * n); dft(b,2 * n) b[i] = (2 * b[i] - c[i] * b[i] % mo * b[i]) % mo;
        dft(b,-1); b.re(n);
    }
    b.re(a.si); return b;
}

V qd(V a) {
    fo(i,a.si - 2) a[i] = a[i + 1] * (i + 1) % mo;
    a.re(a.si - 1);
    return a;
}
V jf(V a) {
    a.re(a.si + 1);
    fd(i,a.si - 1,1) a[i] = a[i - 1] * ksm(i,mo - 2) % mo;
    a[0] = 0;
    return a;
}
 
V ln(V a) {
    int n = a.si;
    a = jf(qd(a) * qni(a));
    a.re(n); 
    return a;
}

V exp(V a) {
    V b; b.re(1); b[0] = 1;
    for(int n = 1; n < a.si * 2; n *= 2) {
        b.re(n);
        V c = a; c.re(n);
        V d = ln(b);
        ff(i,n) d[i] -= c[i];
        d = d * b;
        ff(i,n) b[i] = (b[i] - d[i] + mo) % mo;
    }
    b.re(a.si); return b;
}

const int N = 1e5 + 5;

int n,m,a[N],b[N];
ll fac[N],nf[N];

void build(int n) {
    fac[0] = 1;
    fo(i,n) fac[i] = fac[i - 1] * i % mo;
    nf[n] = ksm(fac[n],mo - 2);
    fd(i,1) nf[i - 1] = nf[i] * i % mo;
}

V p;

V mul(V a,V b) {
    a = a * b;
    a.re(m);
    fd(i,m - 1,1) a[i] = (a[i] + a[i - 1]) % mo;
    return a;
}

V c;

V ksm(V x,int y) {
    if(y == 1) return x;
    ll xc = x[0]; ll nc = ksm(xc,mo - 2);
    ff(i,m) x[i] = x[i] * nc % mo;
    x = ln(x);
    ff(i,m) x[i] = x[i] * y % mo;
    x = exp(x);
    xc = ksm(xc,y);
    ff(i,m) x[i] = x[i] * xc % mo;
    V d = c;
    ff(i,m) d[i] = d[i] * (y - 1) % mo;
    d = exp(d);
    x = x * d; x.re(m);
    return x;
}

V operator + (V a,V b) {
    if(a.si < b.si) a.re(b.si);
    ff(i,b.si) a[i] = (a[i] + b[i]) % mo;
    return a;
}

V ans;

int main() {
    ntt :: build();
    build(1e5);
    scanf("%d %d",&m,&n);
    c.re(2); c[0] = 1; c[1] = 1;
    c.re(m); c = ln(c);
    fo(i,n) scanf("%d %d",&a[i],&b[i]);
    fo(i,n) {
        p.clear(); p.re(m);
        ll f = 1;
        fo(j,min(b[i],m)) {
            f = f * (b[i] - j + 1) % mo;
            p[j - 1] = f * nf[j] % mo;
        }
        p = ksm(p,a[i]);
        if(i == 1) ans = p; else ans = mul(ans,p);
    }
    ll as = (ans[m - 1] % mo + mo ) % mo;
    pp("%lldn",as);
}