单位根反演学习笔记

emm...原来反演公式有这么多呀。。。

不多说了，直接进入正题。

$$f(x)=\sum_{i=0}^na_ix^i\Rightarrow \sum_{i=0}^na_i[i\ mod \ k=0]=\frac{1}{k}\sum_{i=0}^{k-1}f(w_k^i)$$

我们考虑证明这个式子。

首先，有一个显而易见的引理。

$$[i \ mod \ k=0]=\frac{1}{k}\sum_{j=0}^{k-1}w_k^{ij}$$

这个式子用等比数列求和公式搞一下就出来了，就不多讲了。

$$\sum_{i=0}^na_i[i \ mod \ k=0]=\frac{1}{k}\sum_{i=0}^n\sum_{j=0}^{k-1}a_iw_k^{ij}=\frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=0}^na_i(w_k^j)^i=\frac{1}{k}\sum_{j=0}^{k-1}f(w_k^i)$$

证毕。

loj6485

题目描述：求$$\sum_{i=0}^nC_n^is^ia_{i\bmod 4} \bmod 998244353$$

首先$$ans=\sum_{j=0}^3a_j\sum_{i=0}^nC_n^is^i[i\bmod 4=j]$$

先考虑$j=0$的时候，构造$f(x)=\sum_{i=0}^nC_n^is^ix^i=(sx+1)^n$

所以$$\sum_{i=0}^nC_n^is^i[i\bmod 4=0]=\frac{1}{4}\sum_{j=0}^3f(w_4^j)$$

但是当$j>0$的时候怎么办呢？我们考虑将$f(x)$乘上$x^{-j}$，就可以让模4余$j$的移到模4余0的位置了。

综上$$ans=\frac{1}{4}\sum_{j=0}^3f(w_4^j)\sum_{i=0}^3a_iw_4^{-ij}$$

 1 #include<cstdio>
 2 #define Rint register int
 3 using namespace std;
 4 typedef long long LL;
 5 const int mod = 998244353, inv4 = 748683265;
 6 int t;
 7 LL n, s, a[4], w[4];
 8 inline LL kasumi(LL a, LL b){
 9     LL res = 1;
10     while(b){
11         if(b & 1) res = res * a % mod;
12         a = a * a % mod;
13         b >>= 1;
14     }
15     return res;
16 }
17 int main(){
18     scanf("%d", &t);
19     w[0] = 1; w[1] = kasumi(3, (mod - 1) >> 2); w[2] = w[1] * w[1] % mod; w[3] = w[1] * w[2] % mod;
20     while(t --){
21         scanf("%lld%lld", &n, &s); n %= mod - 1;
22         for(Rint i = 0;i < 4;i ++) scanf("%lld", a + i);
23         LL ans = 0;
24         for(Rint j = 0;j < 4;j ++){
25             LL tmp = kasumi((s * w[j] + 1) % mod, n);
26             for(Rint i = 0;i < 4;i ++)
27                 ans = (ans + tmp * a[i] % mod * w[(4 - i * j % 4) % 4]) % mod;
28         }
29         printf("%lld\n", ans * inv4 % mod);
30     }
31 }

bzoj3328

题目描述：求$$\sum_{i=0}^nC_n^iF_i[i\bmod k=0]$$

我们构造矩阵$$\begin{gather*}A=\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}\end{gather*}$$

大家对它应该很熟悉了，它就是斐波那契数列的转移矩阵。

显然$$\begin{gather*}F_i=A^i*\begin{bmatrix}1 \\ 0\end{bmatrix}=A^i_{1,1}\end{gather*}$$

然后构造生成函数$$f(x)=\sum_{i=0}^nC_n^iA^ix^i=(xA+I)^n$$

$$Ans=\sum_{i=0}^nC_n^iA^i[i\bmod k=0]=\frac{1}{k}\sum_{j=0}^{k-1}f(w_k^j)$$

这个矩阵的左上角就是答案。

（话说我是怎么推完式子就写题解的。。。）

（所以没有代码）

单位根反演学习笔记

原文：https://www.cnblogs.com/AThousandMoons/p/10502530.html