题目链接

题意简述

有 $n$ 个烧烤包，每个烧烤包里面有一根棍子， $A_i$ 块牛肉， $B_i$ 块青椒。每根棍子两两不同，每块牛肉和青椒是相同的。Snuke想选取两个烧烤包，然后将所有牛肉和青椒串在棍子上，组成一根烤串。棍子是不可翻转的。求可以组成烤串的种类数模 $10^9+7$ 。

题解

题目就是求

\sum_{i=1}^n \sum_{j=i+1}^n \binom{A_i+B_i+A_j+B_j}{A_i+A_j}

直接求显然会TLE，考虑两个点

x_1,y_1)

到

x_2,y_2)

，只能向上或向右走的方案数，显然为

(x2−x1+y2−y1x2−x1)\binom{x_2-x_1+y_2-y_1}{x_2-x_1}

。因此题目本质上是求

A_i,-B_i)

到

A_j,B_j)

的方案数。dp解决即可。

代码

#include 
    
     #include 
     
      int read(){
      int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {
          if(ch=='-')        {
              f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {
          x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=200000;const int maxm=2001;const int maxk=maxm<<1;const int mod=1000000007;int n,x[maxn+10],y[maxn+10],mp[maxk+10][maxk+10],f[maxk+10][maxk+10],C[maxk*2+10][maxk+10];int main(){
      n=read();  for(int i=1; i<=n; ++i)    {
          int a=read(),b=read();      ++mp[maxm-a][maxm-b];      x[i]=a;      y[i]=b;    }  C[0][0]=1;  for(int i=1; i<=maxk*2; ++i)    {
          C[i][0]=C[i-1][0];      for(int j=1; (j<=i)&&(j<=maxk); ++j)        {
              C[i][j]=C[i-1][j]+C[i-1][j-1];          if(C[i][j]>=mod)            {
                  C[i][j]-=mod;            }        }    }  for(int i=1; i<=maxk; ++i)    {
          for(int j=1; j<=maxk; ++j)        {
              f[i][j]=mp[i][j]+f[i-1][j]+f[i][j-1];          if(f[i][j]>=mod)            {
                  f[i][j]-=mod;            }        }    }  int ans=0;  for(int i=1; i<=n; ++i)    {
          ans+=f[x[i]+maxm][y[i]+maxm];      if(ans>=mod)        {
              ans-=mod;        }      ans-=C[(x[i]+y[i])<<1][x[i]<<1];      if(ans<0)        {
              ans+=mod;        }    }  ans=1ll*ans*((mod+1)/2)%mod;  printf("%d\n",ans);  return 0;}

转载于:https://www.cnblogs.com/Canopus-wym/p/10376099.html

你可能感兴趣的文章