D.Integers Have Friends

题目链接

Integers Have Friends

简要题解

E.The Three Little Pigs

题目链接

The Three Little Pigs

简要题解

我们先来考虑一个询问的情况，看看最终答案是什么样子的。
题目说道，两个攻击方案不同，当且仅当攻击时刻不同，以及攻击对象不同。
那么我们很自然能够想到，枚举攻击时刻，利用组合数来计算攻击对象的方案，求和得到答案。
对于一个询问\(x\)，它对应的答案为：$$Ans=\sum_{i=0}^n C_{3*i}^x$$
预处理组合数，每次询问就可以\(O(n)\)解决，但是这并不能通过本题。

由于答案是组合数的和，我们可以从组合数的性质来入手。
有一个众所周知的公式：\(C_i^j=C_{i-1}^j+C_{i-1}^{j-1}\)
把这个公式代入答案的计算公式，我们得到：

\[\sum_{i=0}^n C_{3*i}^x =\sum_{i=0}^n C_{3*i-1}^x+\sum_{i=0}^n C_{3*i-1}^{x-1} \]

这个时候就发现了一些有意思的东西。我们设\(A[x][j]=\sum_{i=0}^{n-(j\neq 0)} C_{3*i+j}^x\)，那么上式可以写成

\[A[x][0]=A[x-1][2]+A[x][2] \tag{1} \]

同理，我们可以得到

\[A[x][1]=(A[x-1][0]-C_{3*n}^{x-1}) +(A[x][0]-C_{3*n}^x) \tag{2} \]

\[A[x][2]=A[x-1][1]+A[x][1] \tag{3} \]

这三个方程线性相关，我们目前无法求解。
再次利用组合数的性质，我们把\(A[x][0],A[x][1],A[x][2]\)加起来，可以得到：

\[A[x][0]+A[x][1]+A[x][2]=\sum_{i=0}^{3*n}C_{i}^x=C_{3*n+1}^{x+1} \tag{4} \]

联立上述四个式子就可以解方程，再预处理组合数，就可以得到\(O(1)\)递推式。
那么思路就很清楚了：我们先得到\(A[0][0],A[0][1],A[0][2]\)的值，然后递推求出所有的\(A[x][0],A[x][1],A[x][2]\)。
对于每一个询问\(x\)，我们直接输出\(A[x][0]\)。
时间复杂度\(O(n)\)。
代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e6+10;
const int Mod=1e9+7;
int n,Qs,Ans,Inv3,Two,A[MAXN][3];
int Read()
{   int a=0,c=1;   char b=getchar();
    while(b!='-'&&(b<'0'||b>'9')) b=getchar();
    if(b=='-') c=-1,b=getchar();
    while(b>='0'&&b<='9') a=a*10+b-48,b=getchar();
    return a*c;
}
int Pow(int Down,int Up)
{   int Ret=1,Now=Down;
    for(;Up>=1;Up>>=1) Up&1?Ret=1ll*Ret*Now%Mod:0,Now=1ll*Now*Now%Mod;
    return Ret;
}
namespace PRE
{   int Inv[MAXN],Fac[MAXN];
    void Prepare()
    {   Fac[0]=Inv[0]=1,Inv3=Pow(3,Mod-2),A[0][0]=n+1,A[0][1]=A[0][2]=n;
        for(int i=1;i<=3*n+1;i++) Fac[i]=1ll*Fac[i-1]*i%Mod;
        Inv[3*n+1]=Pow(Fac[3*n+1],Mod-2);
        for(int i=3*n;i>=0;i--) Inv[i]=1ll*Inv[i+1]*(i+1)%Mod;
    }
}using namespace PRE;
int C(int A,int B){   return B>A?0:1ll*Fac[A]*Inv[B]%Mod*Inv[A-B]%Mod;   }
int main()
{   n=Read(),Qs=Read(),Prepare();
    for(int i=1;i<=n*3;i++)
    {   int B0=A[i-1][0],B1=A[i-1][1],B2=A[i-1][2],Nc=C(3*n+1,i+1),Sc=C(3*n,i);
        B0=(1ll*B0+Mod-C(3*n,i-1))%Mod;
        A[i][0]=(1ll*Nc+Sc-B0+B2)*Inv3%Mod,A[i][0]=(A[i][0]+Mod)%Mod;
        A[i][1]=(1ll*Nc-2*Sc+2*B0+B2)*Inv3%Mod,A[i][1]=(A[i][1]+Mod)%Mod;
        A[i][2]=(1ll*Nc+Sc-B0-2*B2)*Inv3%Mod,A[i][2]=(A[i][2]+Mod)%Mod;
    }
    for(int i=1,S;i<=Qs;i++) S=Read(),printf("%d\n",A[S][0]);
}