Problem

[AGC001E] BBQ Hard 。

计算

其中 \(n \leq 2 \times 10^5\) ， \(a_i,b_i \leq 2000\) 。

Solution

以 \(a_i\) 代 \(a_i+b_i\) 则等价于求 。

考虑使得式子变得更加对称，我们可以不限制 \(i,j\) 的相对大小，之后减去 \(i=j\) 的情况再除以 \(2\) 即可.

问题转化为求 。

代数法

推导过程

考虑将 \(i,j\) 拆开分别计算贡献，可以联想到 Vandermonde卷积 于是原式转换为 。

其中 \(F(k)=\displaystyle\sum_{i=1}^n\binom{t_i}{a_i+k}\) 。

然后我们容易想到一个 \(O(na)\) 的做法，那就是直接计算 \(F(k)\) ，注意由于 \(k\) 的范围是 \([-2000,2000]\) ，所以我们需要将 \(k\) 平移至 \([0,4000]\) ，这样就可以用一个数组来存储 \(F(k)\) 了.

                        
                          for (int k = mink; k <= maxk; ++k) {
    for (int i = 1; i <= n; ++i) {
        if (k + b[i] >= 0 && k + b[i] <= a[i]) {
            F[k + SHIFT] = (F[k + SHIFT] + C[a[i]][k + b[i]]) % MOD;
        }
    }
}

                        
                      

优化

这个也许卡卡常就能过了，但是我们尝试去追求更好的时间复杂度 事实上，我们利用生成函数的相关知识，有 。

其中 \([x^i]\) 表示 \(x^i\) 项的系数。 则我们只需要求出 。

这个式子可以用秦九韶算法来求，复杂度降低至 \(O(a^2)\) 。

                        
                          for (int i = 1; i <= n; ++i) {
    bInA[a[i]].push_back(-b[i] + SHIFT);
}
for (int i = maxa; i >= 0; --i) {
    for (int k = 2* SHIFT; k >= 1; --k) {
        F[k] = (F[k] + F[k - 1]) % MOD;
    }
    for (auto bInAi : bInA[i]) {
        F[bInAi] = (F[bInAi] + 1) % MOD;
    }
}

                        
                      

完整代码

                        
                          #include<iostream>
#include<vector>
using namespace std;
const int MAX_N = 200005, MOD = 998244353, MAX_A = 4000 + 5, SHIFT = 2000;
int ans, n, a[MAX_N], b[MAX_N], maxa, C[MAX_A][MAX_A], mink, maxk;
int fac[MAX_A * 2], inv[MAX_A * 2], invfac[MAX_A * 2];
int F[MAX_A];//from -2000 to 2000, 加上基数2000
int binom(int n, int k) {
    if (n < k) {
        return 0;
    }
    return 1ll * fac[n] * invfac[k] % MOD * invfac[n - k] % MOD;
}
vector<int> bInA[MAX_A];
signed main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        a[i] += b[i];
        maxa = max(maxa, a[i]);
        mink = min(mink, -b[i]);
        maxk = max(maxk, a[i] - b[i]);
    }
    for (int i = 0; i <= maxa; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
    }
    /*for (int k = mink; k <= maxk; ++k) {
        for (int i = 1; i <= n; ++i) {
            if (k + b[i] >= 0 && k + b[i] <= a[i]) {
                F[k + SHIFT] = (F[k + SHIFT] + C[a[i]][k + b[i]]) % MOD;
            }
        }
    }*/
    for (int i = 1; i <= n; ++i) {
        bInA[a[i]].push_back(-b[i] + SHIFT);
    }
    for (int i = maxa; i >= 0; --i) {
        for (int k = 2* SHIFT; k >= 1; --k) {
            F[k] = (F[k] + F[k - 1]) % MOD;
        }
        for (auto bInAi : bInA[i]) {
            F[bInAi] = (F[bInAi] + 1) % MOD;
        }
    }

    for (int k = mink; k <= maxk; ++k) {
        ans = (ans + 1ll * F[k + SHIFT] * F[-k + SHIFT] % MOD) % MOD;
    }
    fac[0] = inv[0] = invfac[0] = 1;
    fac[1] = inv[1] = invfac[1] = 1;
    for (int i = 2; i <= maxa * 2; ++i) {
        fac[i] = 1ll * fac[i - 1] * i % MOD;
        inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;
        invfac[i] = 1ll * invfac[i - 1] * inv[i] % MOD;
    }
    for (int i = 1; i <= n; ++i) {
        ans = (ans - binom(2 * a[i], 2 * b[i]) + MOD) % MOD;
    }
    ans = 1ll * ans * inv[2] % MOD;
    cout << ans << endl;
    return 0;
}


                        
                      

组合意义法

我们可以把这个值看做在网格图上的一点 \((−a[i],−b[i])\) 走到 \((a[j],b[j])\) 的方案数。 而网格图走的方案数可以直接递推得到。 那么我们对于每个点把它的坐标取反到第三象限，然后对于整个坐标系计算走到每一个格子的总方案.

递推式与网格路径完全相同 。

                        
                          f[i][j] = (1ll * f[i][j] + f[i - 1][j] + f[i][j - 1]) % MOD;

                        
                      

需要注意的是初始条件 。

                        
                          for(int i = 1; i <= n; i++){
    f[SHIFT - a[i]][SHIFT - b[i]]++;
} 

                        
                      

最后此篇关于[AGC001E]BBQHard题解的文章就讲到这里了,如果你想了解更多关于[AGC001E]BBQHard题解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。