loj6485 LJJ学二项式定理

$$ \sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^ia_{i\text{mod}4}}=\sum_{0\le j\le 3}{a_j\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\left[ i\equiv j\left( mod\,\,4 \right) \right]}} \\ =\sum_{0\le j\le 3}{\begin{array}{c} a_j\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\left[ i-j\equiv 0\left( mod\,\,4 \right) \right]}\\ \end{array}} \\ \text{令}\omega _4\text{为模998244353意义下的四次单位根，则有}\sum_{0\le i<3}{\omega _{4}^{i}}=0 \\ \text{显然对于任意非零的}k,\text{有}\sum_{0\le i<3}{\omega _{4}^{ik}}=\text{0,而对于}k=\text{0则有}\sum_{0\le i<3}{\omega _{4}^{ik}}=4 \\ \text{故}\sum_{0\le j\le 3}{a_j\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\left[ i-j\equiv 0\left( mod\,\,4 \right) \right]}}=\sum_{0\le j\le 3}{\begin{array}{c} a_j\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\frac{1}{4}\sum_{0\le k\le 3}{\omega _{4}^{k\left( i-j \right)}}}\\ \end{array}} \\ \text{当且仅当}i-j=0\left( \text{mod}4 \right) \text{时，有}\frac{1}{4}\sum_{0\le k\le 3}{\omega _{4}^{k\left( i-j \right)}}=1 \\ \sum_{0\le j\le 3}{\begin{array}{c} a_j\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\frac{1}{4}\sum_{0\le k\le 3}{\omega _{4}^{k\left( i-j \right)}}}\\ \end{array}}=\frac{1}{4}\sum_{0\le j\le 3}{a_j\sum_{0\le k\le 3}{\omega _{4}^{-kj}\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\omega _{4}^{ki}}}} \\ =\frac{1}{4}\sum_{0\le j\le 3}{\begin{array}{c} a_j\sum_{0\le k\le 3}{\omega _{4}^{-kj}\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) s^i\left( \omega _{4}^{k} \right) ^i}}\\ \end{array}} \\ =\frac{1}{4}\sum_{0\le j\le 3}{\begin{array}{c} a_j\sum_{0\le k\le 3}{\omega _{4}^{-kj}\left( s\omega _{4}^{k}+1 \right) ^n}\\ \end{array}} \\ $$

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#define debug(x) std::cout << #x << " = " << x << std::endl;

typedef long long int int_t;

using std::cin;
using std::endl;
using std::cout;

const int_t mod = 998244353;

int_t power(int_t base,int_t index) {
	int_t result=1;
	index=(index%(mod-1)+mod-1)%(mod-1);
	while(index) {
		if(index&1) result=result*base%mod;
		index>>=1;
		base=base*base%mod;
	}
	return result;
}
int main() {
	int_t T;
	cin>>T;
	const int_t g4=power(3,(mod-1)/4);
	while(T--) {
		int_t n,s;
		static int_t a[4];
		scanf("%lld%lld",&n,&s);
		for(int_t i=0; i<=3; i++)scanf("%lld",&a[i]);
		int_t result=0;
		for(int_t j=0; j<=3; j++) {
			int_t sum=0;
			for(int_t k=0; k<=3; k++) {
				sum=(sum+power(g4,-k*j)*power(1+s*power(g4,k)%mod,n)%mod)%mod;
			}
			sum=sum*a[j]%mod;
			result=(result+sum)%mod;
		}
		result=result*power(4,-1)%mod;
		printf("%lld\n",result);
	}
	return 0;
}