HIT 校测 Round1 F - dp - 二项式定理 -

题意：求\(x\in [0,10^n)\)的个数，使得\(4|x\)且\(x\)中数码4的个数为4的倍数，\(n\leq 10^{16}\)

题解：
第一个条件可以转化为末两位为4的倍数。易知其中不含数码4的有18个，含1个数码4的有6个，2个有1个。
先考虑不含数码4的，剩下\(t=n-2\)位如何处理（判掉n=1或2的）。显然答案就是\(C_{t}^{0}*9^t+C_{t}^{4}*9^{t-4}+...\)
如何计算？联想到二项式定理。但是如何只保留4的倍数项？
这个trick P大夏令营出过原题，只不过当时是3的倍数项。3b1b也有个类似的视频，在讲生成函数的这一期
考虑\((9+w)^{t}=C_{t}^{0}9^t+C_{t}^{1}9^{t-1}*w+C_{t}^{2}9^{t-2}*w^2+C_{t}^{3}9^{t-3}*w^3+...\)
我现在只想保留0,4,8..项。考虑到可以利用模意义下的单位根\(w+w^2+w^3+w^4=0\)来构造消去。即\(w^4=1(\mod 998244353)\)，跑一下发现\(w=86583718\)，也恰好满足\(w+w^2+w^3+w^4=0\)的条件。构造式子如下：
\({1}\over{4}\)\(((9+w)^{t}+(9+w^2)^t+(9+w^3)^t+(9+w^4)^t)\)，即可得到上式，这块答案乘以18即可

再考虑含2个数码4的，答案就是\(C_{t}^{2}*9^{t-2}+...\)，发现能和上面组成一个完整的偶数项。高中技巧w=1和-1代入相加除以2即可

在考虑含1个数码4的，即求\(C_{t}^{3}*9^{t-3}+...\)思路还是消项，经过构造发现答案就是\({1}\over{4}\)\(*(w*(9+w)^{t}+w^2*(9+w^2)^t+w^3*(9+w^3)^t+w^4*(9+w^4)^t)\)，最后乘以6即可

时间复杂度\(O(logn)\)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#define mpr make_pair
#define debug() cerr<<"Madoka\n"

using namespace std;

typedef long long LL;
int mod=998244353;
#define int LL
// 18 0; 6 1; 1 2

int pw(int x,int y){
	if(!y)return 1;if(y==1)return x;
	int mid=pw(x,y>>1);
	if(y&1)return 1ll*mid*mid%mod*x%mod;
	return 1ll*mid*mid%mod;
}

int pp = 86583718,ppp,pppp,ppppp;

void solve(){
	int n;scanf("%lld",&n);
	if(n == 1)puts("2");
	else if(n == 2)puts("18");
	else{
		int t1=pw(9+pp,n-2),t2=pw(9+ppp,n-2),t3=pw(9+pppp,n-2),t4=pw(9+ppppp,n-2),inv=pw(4,mod-2);
		int ans1 = (((t1+t2)%mod+(t3+t4)%mod)%mod) * inv%mod;
		int ans2 = (pw(10,n-2) + pw(8,n-2))%mod*pw(2,mod-2) - ans1;
		ans2 = (mod+ans2)%mod;
		int ans3 = ((pp*t1%mod+ppp*t2%mod)%mod + (pppp*t3%mod + ppppp*t4%mod)%mod)%mod*inv%mod;
		printf("%lld\n",((ans1*18ll%mod + ans2)%mod + ans3*6ll%mod)%mod);
	}
}

signed main(){
	ppp=1ll*pp*pp%mod, pppp = 1ll*ppp*pp%mod, ppppp=1ll*pppp*pp%mod;
	int te;scanf("%lld",&te);
	while(te--)solve();
	
	return 0;
}

标算写的矩阵快速幂优化dp，我应该是唯一写了这种做法的人。