[AGC001E] BBQ Hard

· · 题解

大佬口中所说的经典题。

组合意义天地灭，代数推导保平安。

考虑先将题目柿子的限制弄小一点。

\sum\limits_{i=1}^{n}\sum\limits_{j=1}^n \binom{a_i+b_i+a_j+b_j}{a_i+a_j}

然后大力推导。

\begin{aligned} & \sum\limits_{i=1}^{n}\sum\limits_{j=1}^n \binom{a_i+b_i+a_j+b_j}{a_i+a_j}\\ =& [x^{a_i+a_j}]\sum\limits_{i=1}^{n}\sum\limits_{j=1}^n (1+x)^{t_i+t_j} & t_i=a_i+b_i\\ =& [x^0]\sum\limits_{i=1}^{n}\sum\limits_{j=1}^n x^{-a_i-a_j}(1+x)^{t_i+t_j}\\ =&[x^0]\left( \sum\limits_{i=1}^{n}x^{-a_i}(1+x)^{t_i}\right)^2\\ =&[x^0]\left( \sum\limits_{i=1}^{m}Q_i(1+x)^i\right)^2 & Q_k=\sum\limits_{t_i=k}x^{-a_i}\\ \end{aligned}

发现最后一个柿子可以用秦九韶算法快速计算，卷积暴力卷即可。

然后回到原题，修一修边界即可。

时间复杂度 O(n+m^2)。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=8000,c=4000;
const int mo=1e9+7;
int n,a[200010],b[200010],fac[8010],inv[8010],ans,Ans[8010],mx;
vector<int> Q[8010];
inline int ksm(int x,int y)
{
    int ret=1;
    for (;y;y>>=1)
    {
        if (y&1) ret=1ll*ret*x%mo;
        x=1ll*x*x%mo;
    }
    return ret;
}
inline int C(int x,int y){return 1ll*fac[x]*inv[y]%mo*inv[x-y]%mo;}
void mul()
{
    for (int i=N;i>=1;i--)
        Ans[i]=(Ans[i]+Ans[i-1])%mo;
}
int main()
{
    fac[0]=1;inv[0]=1;
    for (int i=1;i<=N;i++) fac[i]=1ll*fac[i-1]*i%mo;
    inv[N]=ksm(fac[N],mo-2);
    for (int i=N-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%mo;
    scanf("%lld",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        Q[a[i]+b[i]].push_back(-a[i]+c);
        mx=max(mx,a[i]+b[i]);
    }
    for (int i=c;i;i--)
    {
        for(auto v:Q[i])
            Ans[v]=(Ans[v]+1)%mo;
        mul();
    }
    for (int i=-c;i<=c;i++) 
        ans=(ans+1ll*Ans[c-i]*Ans[c+i]%mo)%mo;
    for (int i=1;i<=n;i++)
        ans=(ans-C(2*a[i]+2*b[i],2*a[i])%mo+mo)%mo;
    ans=1ll*ans*inv[2]%mo;
    printf("%lld\n",ans);
    return 0;
}