[AGC001E] BBQ Hard题解

这篇具有很好参考价值的文章主要介绍了[AGC001E] BBQ Hard题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

[AGC001E] BBQ Hard题解

Problem

[AGC001E] BBQ Hard

计算:

\[\sum_{i=1}^{n}\sum_{j=i+1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j} \]

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

Solution

\(a_i\)\(a_i+b_i\)则等价于求

\[\sum_{i=1}^{n}\sum_{j=i+1}^n\binom{a_i+a_j}{b_i+b_j} \]

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

\[\sum_{i = 1}^{n}\sum_{j = i + 1}^{n}\binom{a_i+a_j}{b_i+b_j}= \dfrac{1}{2}\left( \sum_{i = 1}^{n}\sum_{j = 1}^{n}\binom{a_i+a_j}{b_i+b_j}-\sum_{i = 1}^{n}\binom{2a_i}{2b_i}\right) \]

问题转化为求

\[\sum_{i=1}^{n}\sum_{j=1}^n\binom{a_i+a_j}{b_i+b_j} \]

代数法

推导过程

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

\[\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^n\binom{a_i+a_j}{b_i+b_j} &=\sum_{i=1}^{n}\sum_{j=1}^n\sum_k\binom{a_i}{b_i-k}\binom{a_j}{b_j+k} \\ &=\sum_k\sum_{i=1}^{n}\sum_{j=1}^n\binom{a_i}{b_i-k}\binom{a_j}{b_j+k} \\ &=\sum_k\left(\sum_{i=1}^{n}\binom{a_i}{b_i-k}\right)\left(\sum_{j=1}^n\binom{a_j}{b_j+k}\right) \\ &=\sum_{k}F(k)F(-k) \end{aligned} \]

其中\(F(k)=\displaystyle\sum_{i=1}^n\binom{a_i}{b_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;
        }
    }
}

优化

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

\[\begin{aligned} F(k)&=\sum_{i=1}^n\binom{a_i}{b_i+k}\\ &= \sum_{i=1}^n(1+x)^{a_i}[x^{b_i+k}]\\ &=[x^k]\sum_{i=1}^n(1+x)^{a_i}x^{-b_i}\\ &=[x^{k+SHIFT}]\sum_{i=1}^n(1+x)^{a_i}x^{-b_i+SHIFT}\\ &=[x^{k+SHIFT}]\sum_{A}(1+x)^A\sum_{i,a_i=A}x^{-b_i+SHIFT} \end{aligned} \]

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

\[\sum_{A}(1+x)^A\sum_{i,a_i=A}x^{-b_i+SHIFT} \]

这个式子可以用秦九韶算法来求,复杂度降低至\(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;

需要注意的是初始条件文章来源地址https://www.toymoban.com/news/detail-442852.html

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

到了这里,关于[AGC001E] BBQ Hard题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Python钢筋混凝土结构计算.pdf-T001-混凝土强度设计值

    以下是使用Python求解上述问题的完整代码: # 输入参数 f_ck = 35   # 混凝土的特征抗压强度(单位:MPa) f_cd = 25   # 混凝土的强度设计值(单位:MPa) # 求解安全系数 gamma_c = f_ck / f_cd # 输出结果 print(\\\"适当的安全系数:{:.2f}\\\".format(gamma_c)) 运行以上代码后,将得到以下输出结果

    2024年02月10日
    浏览(38)
  • display timing值的计算与修改

    一、值的意义 下面是一组参考的timing设置: 这里面主要有几个值需要注意:像素之中pixel clock,也就是timing中的clock-frequency,该值是通过下面h和v开头的参数计算出来的,hactive、vactive这些参数可以通过屏的参考手册找到。通常适配一款屏幕这些参数需要做相应的调整。 二、计

    2024年02月11日
    浏览(27)
  • 【题解】U405180 计算平方和

    欢迎大家在评论区抢前排! 目录 (mathbf{Part 0}) 目录 (/ mathbf{Contents}) (mathbf{Part 1}) 题目大意 (/ mathbf{Item content}) (mathbf{Part 2}) 题解 (/ mathbf{Solution}) (mathbf{Part 2.1}text{ C}) + + 神奇整数类型之 (text{__int128 }/ mathbf{C}) + + (mathbf{Magic integer type}text{ __int128})

    2024年02月19日
    浏览(45)
  • HAUE计算机学院OJ题解

    HAUE河工计院OJ1001 - 1050题解  HAUE河工计院OJ1050 - 1100题解  HAUE河工计院OJ1100 - 1150题解

    2024年02月10日
    浏览(40)
  • 计算机网路学习-time_wait过多

    netstat -an|awk ‘/tcp/ {print $6}’|sort|uniq -c netstat -an 列出系统中所有处于活动状态的网络连接信息,包括 IP 地址、端口号、协议等。 其中,第六列是tcp的状态。 awk ‘/tcp/ {print $6}’ 按行进行匹配,筛选出包含 tcp 的行,只输出符合条件的结果 过滤 TCP 类型的连接,然后输出连接

    2024年02月09日
    浏览(41)
  • 【学习笔记】[AGC021F] Trinity

    第一步有点难😅 考虑加入每一列,发现我们只关心当前还未确定的行的数目 设 d p i , j dp_{i,j} d p i , j ​ 表示有 i i i 列,其中 j j j 行未确定的方案数。钦定每一列至少有一个黑色格子。 d p i , j = j ( j + 1 ) 2 d p i − 1 , j + ∑ k ≥ 1 ∑ k ≤ l ≤ j ( j − l + 1 ) ( l k ) d p i − 1 , j

    2024年02月12日
    浏览(75)
  • AGC004B Colorful Slimes

    题目链接:Colorful Slimes 思路:挺神奇的$dp$ 一个比较显然的结论:最小值的方案中第$2$种操作最多用$n-1$次 证明大概就是一个数用$n-1$次一定会变成另一个数 下面说说$dp$的思路: $dp[i][j]$表示能用最多$j$次第$2$种操作能变成$a_i$的最小值 假设$a_k$所有可以用最多$j$次第$2$种操作

    2024年02月08日
    浏览(31)
  • Atcoder-AGC033C

    看到这道题,是个博弈论,没见过树上的,于是想到在数列里的博弈论,又联想到树的特殊形式————链。 于是我们来讨论一下链的情况(对于没有硬币的点,我们就视为它被删掉了): 讨论链的情况 发现若是选择两端的点,顶点数会减一;若是选择中间的点,顶点数会

    2024年02月08日
    浏览(45)
  • 鸿蒙原生应用/元服务实战-AGC团队账户

    多人及内外结合去开发运营鸿蒙原生应用元服务时,需要用到团队账户,AGC提供了强大的团队角色与权限分工能力。 团队帐号是开发者联盟为实名开发者提供的多个成员帐号登录与权限管理服务。当前团队帐号支持成员参与应用市场(付费推广、应用内付费除外)开发、运营

    2024年01月20日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包