自动搬运

查看原文

来自洛谷，原作者为

	明月夜 May all the beauty be blessed

搬运于2025-08-24 22:15:52，当前版本为作者最后更新于2020-12-04 17:08:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前置芝士：

二项式定理：

$$(x+y)^n=\sum_{i=1}^nC_n^ix^iy^{n-i}$$

卢卡斯定理：

$$Lucas(n,m,p)=C_{n \bmod p}^{m \bmod p}Lucas(n/p,m/p,p) $$

颓一下柿子

$$(x^2+x+1)^n=((x-1)^2+3x)^n=\sum_{i=1}^nC_n^i(x-1)^{2i}(3x)^{n-i} $$

可以发现除了 $C_n^n(x-1)^{2n}$ 这一项，其他项系数的因子都有 $3$

显然是没有意义的

所以只要考虑 $(x-1)^{2n}$ 中第 $i$ 项的系数

$$(x-1)^{2n}=\sum_{i=1}^{2n}C_{2n}^ix^{i}(-1)^{2n-i} $$

第 $i$ 项系数即 $C_{2n}^{i}(-1)^{2n-i}$

卢卡斯定理求一下就好了

★,°:.☆(￣▽￣)/$:.°★ 。

码风毒瘤莫喷

#include<bits/stdc++.h>
#define R register
#define LL long long
using namespace std;
inline long long read(){
	long long x=0,d=1; char y=getchar();
	while(y<'0'||y>'9'){if(y=='-')d=-1;y=getchar();}
	while(y>='0'&&y<='9'){x=(x<<3)+(x<<1)+(y^'0');y=getchar();}
	return x*d;
}
int k;
LL n,i,fact[4],ny[4];
int Cn(int a,int b){return a>b?0:fact[b]*ny[a]*ny[b-a]%3;}
int lucas(LL a,LL b){return b?lucas(a/3,b/3)*Cn(a%3,b%3)%3:1;}
int main(){
	k=read();
	fact[0]=fact[1]=ny[0]=ny[1]=1;
	fact[2]=ny[2]=2;
	while(k--){
		n=read(); i=read();
		printf("%d\n",(lucas(i,n<<1)*(i%2?-1:1)+3)%3);
	}
	return 0;
}