D.Integers Have Friends
题目链接
简要题解
E.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]);
}