单位根反演—简介

单位根反演总的来说不是一个非常难的姿势，但是确实解决某些问题的必要前提
它可以在$O(k)$的时间内求一个数列（或是生成函数）所有下标是$k$的倍数的点值和
$$[k|n]=\frac{1}{k}\sum _{i=0}^{k-1}{\omega }_k^{ni}$$
证明：
如果$k|n$，那么：
$$\frac{1}{k}\sum _{i=0}^{k-1}{\omega }_k^{ni}=\frac{1}{k}\sum _{i=0}^{k-1}({\omega }_k^n{)}^i=\frac{1}{k}\sum _{i=0}^{k-1}{\omega }_k^0=1$$
如果$k\nmid n$，那么根据等比数列求和有：
$$\frac{1}{k}\sum _{i=0}^{k-1}{\omega }_k^{ni}=\frac{1}{k}({\omega }_k^0\cdot \frac{{\omega }_k^0-{\omega }_k^{kn}}{1-{\omega }_k^n})=\frac{1}{k}({\omega }_k^0\cdot \frac{1-1}{1-{\omega }_k^n})=0$$
所以呢这个公式就成立了。

LOJ #6485. LJJ 学二项式定理

公式的处理十分有意思，比如说将$a_{i\mathrm{mod}4}$写成了${\sum }_{j=0}^3{a}_j[i\mathrm{mod}4=j]$，利用sigma来写出公式，这样就朝着单位根反演的方向靠近了。

还有一个求和换序的地方也十分有意思。思想是将含i含n的部分放在一起。

最后的二项式定理是神来之笔，顺利地将一个需要$O(n)$的式子变成了$O(1)$的答案。以后注意到当有组合数和次方时，可以往二项式定理上转换。

实现数学公式的能力还要继续锻炼。

还有一个遗留问题，就是怎么去求4的单位根？

#include
using namespace std;
typedef long long ll;
const ll MOD=998244353;

ll a[10],w[10]={ 1, 911660635, 998244352, 86583718 };

ll qkmod(ll a,ll n)
{
	ll ret=1;
	while(n)
	{
		if(n&1) ret=ret*a%MOD;
		a=a*a%MOD;
		n>>=1;
	}
	return ret;
}

int main()
{
	int Bri;
	scanf("%d", &Bri);
	while(Bri--)
	{
		ll n,s;
		scanf("%lld %lld", &n, &s);
		for(int i=0;i<=3;i++) scanf("%lld", &a[i]);
		ll ans=0;
		for(int i=0;i<=3;i++)
		{
			ll sum=0;
			for(int j=0;j<=3;j++)
			{
//				sum += w[(4 - i) * j % 4] * qkmod(s * w[j] % MOD + 1, n);
//				sum %= MOD;
				( sum += w[(4 - i) * j % 4] * qkmod(s * w[j] % MOD + 1, n) ) %= MOD;
			}
//			ans += sum * a[i];
//			ans %= MOD;
			( ans += sum * a[i] ) %= MOD;
		}
		ans = ans * qkmod(4, MOD - 2) % MOD;
		printf("%lld\n", ans);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47