【51nod】1776 路径计数

我们先把前两种数给排好，排好之后会有\(a + b + 1\)个空隙可以填数，我们计算有\(k\)个空隙两端都是相同字母的方案数

可以用枚举把第二种数分成几段插进去来算，设这个方案数为\(f[k]\)

然后对于一种有\(k\)个空隙的方案数，枚举剩下的\(a + b + 1 - k\)个空隙填了\(h\)个

然后计算把\(C\)和\(D\)分成\(k + h\)段的方案数就好了，记为\(g[k + h]\)

那么如何计算\(g[i]\)呢

一段要么是偶数，\(C\)和\(D\)个数相等，一段要么是奇数，\(C\)多或者\(D\)多

对于一个\(i\)，强制认为\(C\)多的有\(j\)个，那么可以求出\(D\)多的是\(k\)个，剩下的必须两两配对，把剩下的\(i - j - k\)，填成\(DC\)或者\(CD\)，有两种方案

然后剩下的\(CD\)的对子，扔到\(i\)个区间中排列方法是唯一的，只要计算切成\(i\)段每段可以为空的方案数是多少就行了，是个组合数

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define ba 47

#define MAXN 1000005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

        if(c == '-') f = -1;

        c = getchar();

    }

    while(c >= '0' && c <= '9') {

        res = res * 10 +c - '0';

        c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

        out(x / 10);

    }

    putchar('0' + x % 10);

}

const int MOD = 998244353;

int fac[10005],invfac[10005],f[5005],g[5005],pw[5005];

int a[5],N;

int inc(int a,int b) {

    return a + b >= MOD ? a + b - MOD : a + b;

}

int mul(int a,int b) {

    return 1LL * a * b % MOD;

}

void update(int &x,int y) {

    x = inc(x,y);

}

int fpow(int x,int c) {

    int res = 1,t = x;

    while(c) {

        if(c & 1) res = mul(res,t);

        t = mul(t,t);

        c >>= 1;

    }

    return res;

}

int C(int n,int m) {

    if(n < m) return 0;

    return mul(fac[n],mul(invfac[m],invfac[n - m]));

}

int main(){

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    fac[0] = 1;

    for(int i = 1 ; i <= 10000 ; ++i) fac[i] = mul(fac[i - 1],i);

    invfac[10000] = fpow(fac[10000],MOD - 2);

    for(int i = 9999 ; i >= 0 ; --i) invfac[i] = mul(invfac[i + 1],i + 1);

    pw[0] = 1;

    for(int i = 1 ; i <= 5000 ; ++i) pw[i] = mul(pw[i - 1],2);

    while(scanf("%d%d%d%d",&a[0],&a[1],&a[2],&a[3]) != EOF) {

        N = a[0] + a[1] + a[2] + a[3];

        if(!N) {puts("1");continue;}

        memset(f,0,sizeof(f));

        memset(g,0,sizeof(g));

        for(int i = 1 ; i <= a[2] + a[3] ; ++i) {

            for(int j = 0 ; j <= min(i,a[2]) ; ++j) {

                if(a[3] < a[2] - j) continue;

                int k = a[3] - (a[2] - j);

                if(j + k > i) continue;

                if(a[2] - j < i - j - k) continue;

                int t = 1;

                t = mul(t,C(i,j));t = mul(t,C(i - j,k));

                t = mul(t,pw[i - j - k]);

                int rem = a[2] - j - (i - j - k);

                t = mul(t,C(rem + i - 1,i - 1));

                update(g[i],t);

            }

        }

        for(int i = 1 ; i <= a[1] ; ++i) {

            int t = C(a[1] - 1,i - 1);

            for(int k = max(0,i - 2) ; k <= min(a[0] - 1,i) ; ++k) {

                int t0 = t;

                t0 = mul(C(a[0] - 1,k),t0);t0 = mul(t0,C(2,i - k));

                int p = a[0] - 1 - k + a[1] - i;

                update(f[p],t0);

            }

        }

        int ans = 0;

        for(int i = 0 ; i <= a[0] + a[1] ; ++i) {

            if(!f[i]) continue;

            for(int h = a[0] + a[1] + 1 - i ; h >= 0 ; --h) {

                int c = mul(f[i],g[i + h]);

                c = mul(c,C(a[0] + a[1] + 1 - i,h));

                update(ans,c);

            }

        }

        out(ans);enter;

    }

}