系数 题解(lucas+思维)

题目链接

题目思路

这个题目的关键就是 答案模3

要利用这个来突破

令

则

因为

显然只有

那么就可以得证

则

那么

使用lucas求解

时间复杂度

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=3e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int eps=1e-6;
ll n,k;
ll fac[4];
ll cal(ll a,ll b){
    if(a<b) return 0;
    else    return fac[a]/fac[b]/fac[a-b]%3;
}
ll lucas(ll a,ll b){
    if(b==0) return 1;
    return lucas(a/3,b/3)*cal(a%3,b%3)%3;
}
signed main(){
    fac[0]=1;
    for(int i=1;i<=3;i++){
        fac[i]=fac[i-1]*i;
    }
    int _;scanf("%d",&_);
    while(_--){
        scanf("%lld%ld",&n,&k);
        ll ans=lucas(2*n,k);
        if(k%2==1) ans=(-ans+3)%3;
        printf("%lld\n",ans);
    }
    return 0;
}