系数 （牛客）lucas

实际就是求C(2*n,k)%3

代码：

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;ll n,k,t,base;
ll mod=3;
ll apow(ll a,ll b)
{ll s=1;while(b){if(b&1){s=s*a%mod;}a=a*a%mod;b>>=1;}return s;
}
ll C(ll n,ll m)
{if(n<m){return 0;}if(n==m){return 1;}if(m==0){return 1;}ll aa=1,bb=1;for(ll i=n;i>=n-m+1;i--){aa=aa*i%mod;}for(ll i=1;i<=m;i++){bb=bb*apow(i,mod-2)%mod;}return aa*bb%mod;
}
ll lucas(ll n,ll m)
{ll ans=1;while(n&&m){ans=ans*C(n%3,m%3)%mod;n/=3;m/=3;}return ans;
}
int main()
{cin>>t;while(t--){cin>>n>>k;n*=2;if(k%2!=0){cout<<(3-lucas(n,k))%3<<'\n';}else{cout<<lucas(n,k)<<'\n';}}return 0;
}