[ACG001E] BBQ hard [dp]

题面：

传送门

思路：

首先，一个暴力的想法

对于每一对pack，求出f(ai+aj,bi+bj)，其中f(x,y)=(x+y)!/(x!y!)，也就是x个a，y个b的排列方式个数

然后转化模型，将f数组变化成这样的形式：f(x,y)表示一个x行y列的方格图，左下走到右上的方法数

然后将所有的f放到一个图中，就变成了：左下的n个点(-ai,-bi)到右上的n个点(ai,bi)的总方法数（任意一个出发任意一个到达）

用DAGdp把这个方法数求出来，就是sigma(f(ai+aj,bi+bj))(i=1...n,j=1...n)，减去所有的f(ai+ai,bi+bi)再除以二即可

注意：MOD1e9+7意义下，要使用乘法逆元

Code：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define ll long long

 #define MOD 1000000007

 using namespace std;

 inline int read(){

     int re=,flag=;char ch=getchar();

     while(ch>''||ch<''){

         if(ch=='-') flag=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='') re=(re<<)+(re<<)+ch-'',ch=getchar();

     return re*flag;

 }

 const int dx[]={,,},dy[]={,,};

 ll dp[][];int N=;bool vis[][];

 int n,xx[],yy[],qx[],qy[],head=,tail=,maxq=;

 ll inv[],finv[],f[];

 void init(){

     int i;inv[]=finv[]=;

     for(i=;i<=;i++){

         inv[i]=((MOD-MOD/i)*inv[MOD%i])%MOD;

     }

     f[]=;

     for(i=;i<=;i++){

         f[i]=(f[i-]*i)%MOD;

         finv[i]=(finv[i-]*inv[i])%MOD;

     }

 }

 int main(){

     init();

     int i,maxx=,maxy=,x,y,tx,ty;ll X=;

     n=read();

     for(i=;i<=n;i++){

         xx[i]=read();yy[i]=read();

         dp[N-xx[i]][N-yy[i]]+=;

         maxx=max(maxx,xx[i]);maxy=max(maxy,yy[i]);

     }

     qx[]=N-maxx,qy[]=N-maxy;vis[N-maxx][N-maxy]=;

     while(head!=tail){

         x=qx[head];y=qy[head];head=(head+)%maxq;

 //        cout<<"dp "<<x<<ends<<y<<ends<<dp[x][y]<<endl;;

         for(i=;i<=;i++){

             tx=x+dx[i];ty=y+dy[i];

             if(tx>N+maxx||ty>N+maxy) continue;

             dp[tx][ty]=(dp[tx][ty]+dp[x][y])%MOD;

 //            cout<<"    to "<<tx<<ends<<ty<<ends<<dp[tx][ty]<<endl;

             if(!vis[tx][ty]){

                 vis[tx][ty]=;

                 qx[tail]=tx;qy[tail]=ty;tail=(tail+)%maxq;

             }

         }

     }

     for(i=;i<=n;i++){

         X=X+dp[N+xx[i]][N+yy[i]];X%=MOD;

         X=X-((f[xx[i]*+yy[i]*]*finv[xx[i]*])%MOD*finv[yy[i]*])%MOD+MOD;

         X%=MOD;

     }

     printf("%lld\n",(X*inv[])%MOD);

 }

巴特西

[ACG001E] BBQ hard [dp]

最新文章

热门文章