题解 P5947 【[POI2003]Trinomial】

· · 题解

前置芝士：

二项式定理：

(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;
}