题意

\(q(1 \le q \le 10000)\)次询问，每一次求\((x^2+x+1)^n\)的第\(k\)项系数模3。

分析

听说正解是\(\binom{2n}{m} (m \% 2+1)\)，表示不会。

我来一个说一个我yy出来的玄学做法

第\(k\)项的系数就是\(\sum_{i=0}^{k} \binom{n}{i} \binom{i}{k-i} \mod \ 3\)

$$
\begin{align}
& \sum_{i=0}^{k} \binom{n}{i} \binom{i}{k-i} \mod \ 3 \\
= & \sum_{j=0}^{2} \sum_{i=0}^{\left \lfloor \frac{k-j}{3} \right \rfloor} \binom{n \% 3}{(3i+j) \% 3} \binom{\left \lfloor \frac{n}{3} \right \rfloor}{\left \lfloor \frac{3i+j}{3} \right \rfloor} \binom{(3i+j) \% 3}{(k-(3i+j)) \% 3} \binom{\left \lfloor \frac{3i+j}{3} \right \rfloor}{\left \lfloor \frac{k-(3i+j)}{3} \right \rfloor} \mod \ 3 \\
= & \sum_{j=0}^{2} \binom{n \% 3}{j} \binom{j}{(k-j) \% 3} \sum_{i=0}^{\left \lfloor \frac{k-j}{3} \right \rfloor} \binom{\left \lfloor \frac{n}{3} \right \rfloor}{i} \binom{i}{\left \lfloor \frac{k-j}{3} \right \rfloor-i} \mod \ 3\\
\end{align}
$$

然后变成3个子问题，由于可以根据\(\binom{n%3}{j} \binom{j}{(k-j)%3}\)是否为\(0\)还有\(\left \lfloor \frac{k-1}{3} \right \rfloor == \left \lfloor \frac{k-2}{3} \right \rfloor\)之类的强力减枝，所以很快。

虽然理论复杂度是单次查询\(O(k)\)的，不过最后我还是过了= =很快= =

复杂度属于玄学。

题解

分析里说得很清楚了。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int C(int n, int m) {

	return n<m?0:(n==0?1:(n==1?1:(m==1?2:1)));

}

int lucas(ll n, ll m) {

	return m==0?1:(m==1?n%3:(n%3*((n-1)%3)*2%3));

}

int f(ll n, ll k) {

	if(k<=2) {

		int ans=0;

		for(int i=0; i<=k; ++i) {

			ans+=lucas(n, i)*lucas(i, k-i);

		}

		return ans%3;

	}

	int t1=C(n%3, 0)*C(0, (k-0)%3)%3, nx1=t1==0?0:f(n/3, (k-0)/3),

		t2=C(n%3, 1)*C(1, (k-1)%3)%3, nx2=t2==0?0:((t1&&(k%3>0))?nx1:f(n/3, (k-1)/3)),

		t3=C(n%3, 2)*C(2, (k-2)%3)%3, nx3=t3==0?0:((t2&&(k%3>1))?nx2:f(n/3, (k-2)/3));

	return (t1*nx1+t2*nx2+t3*nx3)%3;

}

ll n, k;

int main() {

	int T;

	scanf("%d", &T);

	while(T--) {

		scanf("%lld%lld", &n, &k);

		printf("%d\n", f(n, k));

	}

	return 0;

}