拾起，单位根的记忆

拾起，单位根的记忆

阶：

定义：

性质一：

性质二：

性质三：

性质四：

性质五：

原根：

定义：

原根判定定理：

原根个数定理：

原根存在定理：

求原根的算法:

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
typedef long long ll;
int T,cnt,phi[N],pri[N]; vector<int> factor,ans; bool vis[N];
void init(int n){
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]) pri[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
			vis[i*pri[j]]=true;
			if(i%pri[j]==0){
				phi[i*pri[j]]=phi[i]*pri[j];
				break;
			}
			else phi[i*pri[j]]=phi[i]*phi[pri[j]];
		}
	}
}
int qpow(ll a,ll b,int mod){
	ll res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod; b>>=1;
	} return res;
}
void divide(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			factor.push_back(i);
			while(x%i==0) x/=i;
		}
	}
	if(x>1) factor.push_back(x);
}
bool exist(int n){
	if(n==2||n==4) return 1;
	if(n%2==0) n/=2;
	for(int i=2;pri[i]<=n;i++){
		if(n%pri[i]==0){
			while(n%pri[i]==0) n/=pri[i];
			return n==1;
		}
	}
	return 0;
}
int main(){
	init(1000000); scanf("%d",&T);
	while(T--){
		int n,d; scanf("%d%d",&n,&d);
		if(!exist(n)){
			puts("0\n");
			continue;
		}
		factor.clear(); ans.clear(); divide(phi[n]);
		int g;
		for(int i=1;;i++){
			bool is=1;
			if(__gcd(i,n)!=1) continue;
			for(int j=0;j<factor.size();j++){
				if(qpow(i,phi[n]/factor[j],n)==1){ is=0; break; }
			}
			if(is){ g=i; break; }
		}
		ll power=1;
		for(int s=1;ans.size()<phi[phi[n]];s++){
			power=power*g%n;
			if(__gcd(phi[n],s)==1) ans.push_back(power);
		}
	}
}

单位根反演：

多项式中的问题：

例题：

题目：#6247. 九个太阳

解答：

• $Ans=\frac{1}{k}\sum_{i=0}^{k-1}f(\omega_k^i)$，其中 $[x^i]f(x)=\binom{n}{i}$
• $f(x)=\frac{1}{k}\sum_i \binom{n}{i}x^i=(1+x)^n$
• $Ans=\frac{1}{k}\sum_{i=0}^{k-1}(1+\omega_k^i)^n$

题目：#6485. LJJ 学二项式定理

解答：

• 枚举 $j=i\% 4$，求 $\sum_{i=0}^n \binom{n}{i} s^i a_{j}[4\mid i-j]$
• $Ans=a_j\sum_{i=0}^n\binom{n}{i} s^i\times \frac{1}{4}\sum_{t=0}^{3} \omega_{4}^{ti-tj}$
• 再枚举 $t$，$Ans=\dfrac{a_j}{4\,\omega_4^{tj}}\sum_{i=0}^n \binom{n}{i} (s\times\omega_4^t)^i$
• 后面的式子就是 $(s\times\omega_4^t+1)^n$

题目：P10664 BZOJ3328 PYXFIB

解答：

• 值得注意的是，矩阵乘法和单位根反演是兼容的
• $\begin{bmatrix}F_{i-1}&F_{i-2}\end{bmatrix}\ast \begin{bmatrix}1&1\\1&0\end{bmatrix}=\begin{bmatrix}F_{i}&F_{i-1}\end{bmatrix}$
• $F_i$ 是矩阵的第一项，我们可以求出最终的矩阵，则答案为此矩阵的第一项
• $Ans=\sum_{i=1}^n[k\mid i]\binom{n}{i}G\ast A^i$，其中 $G$ 为初始矩阵，$A$ 为转移矩阵
• 反演可得 $Ans=\frac{G}{k} \sum_{i=0}^{k-1} (A\omega_k^i+E)^n$，其中 $E$ 为单位矩阵

题目：#5370. 循环序列

解答：

• $Ans=\frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{-ix}(1+\omega_n^i)^k$

题目：P5591 小猪佩奇学数学

解答：

• $Ans=\sum_{i=0}^{n} \binom{n}{i}p^i \ast \frac{i-i\bmod k}{k}$
• $Ans=\frac{1}{k} \sum_{i=0}^{n} \binom{n}{i}p^i i -\frac{1}{k}\sum_{i=0}^{n} \binom{n}{i}p^i(i\bmod k)$
• 先不管 $\dfrac{1}{k}$，将式子拆成左右两边处理
• $left=\sum_{i=0}^{n} \binom{n}{i}p^i i$
• $left=n\sum_{i=1}^{n} \binom{n-1}{i-1}p^i$
• $left=np\sum_{i=0}^{n-1}\binom{n-1}{i}p^i$
• $left=np(p+1)^{n-1}$
• $right=\sum_{i=0}^{n} \binom{n}{i}p^i(i \bmod k)$
• $right=\sum_{i=0}^{n} \binom{n}{i}p^i\sum_{t=0}^{k-1}[t=i\bmod k]t$
• $[t=i \bmod k]=[k|i-t]=\frac{1}{k}\sum_{j=0}^{k-1} \omega_{k}^{j(i-t)}$
• $right=\frac{1}{k}\sum_{i=0}^{n} \binom{n}{i}p^i\sum_{t=0}^{k-1}t\sum_{j=0}^{k-1} \omega_{k}^{ji}\omega_{k}^{-jt}$
• 不管 $\frac{1}{k}$，$right \rightarrow \sum_{i=0}^{n} \binom{n}{i}p^i \omega_{k}^{ji}\sum_{t=0}^{k-1}t\sum_{j=0}^{k-1}\omega_{k}^{-jt}$
• $right=(\omega_{k}^{j}p+1)^n\sum_{t=0}^{k-1}t\sum_{j=0}^{k-1}\omega_{k}^{-jt}$
• 枚举 j，不管定值 $(\omega_{k}^{j}p+1)^n$，$right \rightarrow \sum_{t=0}^{k-1}t\omega_{k}^{-jt}$
• 我们知道，$\sum_{i=1}^{n}w^i=\dfrac{w^{n+1}-w}{w-1}$
• 设 $F(n,w)=\sum_{i=0}^{n}iw^i=\sum_{i=1}^{n}iw^i$
• $wF(n,w)=\sum_{i=0}^{n}iw^{i+1}=\sum_{i=1}^{n+1}(i-1)w^{i}$
• $(w-1)F(n,w)=nw^{n+1}-\sum_{i=1}^{n}w^i=nw^{n+1}-\dfrac{w^{n+1}-w}{w-1}$
• $right=\dfrac{1}{\omega_{k}^{-j}-1}\begin{pmatrix}(k-1)\omega_{k}^{-jk} -\dfrac{(\omega_{k}^{-jk}-\omega_{k}^{-j})}{\omega_{k}^{-j}-1}\end{pmatrix}$
• $right=\dfrac{1}{\omega_{k}^{-j}-1}\begin{pmatrix}(k-1) -\dfrac{1-\omega_{k}^{-j}}{\omega_{k}^{-j}-1}\end{pmatrix}=\dfrac{k}{\omega_{k}^{-j}-1}$
• 综上，$Ans=\dfrac{1}{k} \begin{pmatrix}np(p+1)^{n-1}-\sum_{j=0}^{k-1}\dfrac{(\omega_{k}^{j}p+1)^n}{\omega_{k}^{-j}-1}\end{pmatrix}$，注意讨论 $\omega_{k}^{-j}=1$ 的情况

题目：P10084 [GDKOI2024 提高组] 计算

解答：

• 构造生成函数 $f(x)=\prod_{i=1}^n(1+x^i)$，则 $[x^k]f(x)$ 就是子集和为 $k$ 的子集个数
• 不难得到，$Ans=\sum_{i} [x^i]f(x)[k\mid i]$
• $Ans=\frac{1}{k}\sum_{i=0}^{k-1} f(\omega_k^i)$
• 考虑求 $f(\omega_k^i)$，设 $d=\gcd(i,k)$，则 $f(\omega_k^i)=f\left(\omega_{\frac{k}{d}}^{\frac{i}{d}}\right)$
• $f\left(\omega_{\frac{k}{d}}^{\frac{i}{d}}\right)=\left(\prod\limits_{i=0}^{\frac{k}{d}-1} \left(1+\omega_{\frac{k}{d}}^i\right) \right)^\frac{nd}{k}$
• 我们知道 $x^n-1=\prod_{i=0}^{n-1} (x-\omega_n^i)$，代入 $x=-1$，得 $(-1)^n-1=\prod_{i=0}^{n-1} (-1-\omega_n^i)\Rightarrow\prod_{i=0}^{n-1} (1+\omega_n^i)=1-(-1)^n$
• $f\left(\omega_{\frac{k}{d}}^{\frac{i}{d}}\right)=\left(1-(-1)^{\frac{k}{d}} \right)^\frac{nd}{k}$，可见当 $2\nmid\frac{k}{d}$ 时有贡献
• $Ans=\frac{1}{k}\sum_{d\mid k} 2^{\frac{nd}{k}}\sum_{i}[(i,k)=d][2\nmid \frac{k}{d}]$
• $Ans=\frac{1}{k}\sum_{d\mid k} 2^{\frac{nd}{k}}\varphi(\frac{k}{d})[2\nmid \frac{k}{d}]$
• 设 $k=u\times 2^m$，其中 $2\nmid u$，则 $d=v\times 2^m$ 才满足 $[2\nmid \frac{k}{d}]$
• 最终可得 $Ans=\frac{1}{k}\sum_{d\mid u} 2^{\frac{nd}{u}}\varphi(\frac{u}{d})$

题目：P6800 【模板】Chirp Z-Transform

解答：

• $F(c^i)=\sum_{j} a^j c^{ij}$
• 人类智慧：$ij=\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}$
• $F(c^i)=c^{-\binom{i}{2}}\sum_{j} a^jc^{-\binom{j}{2}}\times c^{\binom{i+j}{2}}$
• 记 $A_{m-i}= a^ic^{-\binom{i}{2}}$，$B_{i}=c^{\binom{i}{2}}$
• $F(c^i)=c^{-\binom{i}{2}}\sum_{j} A_{m-j}\times B_{i+j}$，发现是卷积，可做

题目：P5293 [HNOI2019] 白兔之舞

解答：

• 先定 $t$，$\sum_{i=0}^L \binom{L}{i}[i\equiv t \pmod{k}]W^i=\frac{1}{k}\sum_{i=0}^{k-1} \omega_{k}^{-it} (W\omega_k^i+E)^L$
• 构造多形式 $f(x)$，满足 $[x^i]f(x)=\frac{1}{k}(W\omega_k^i+E)^L$
• $Ans_t=\sum_{i=0}^{k-1} \omega_{k}^{-it}[x^i]f(x)=f(\omega_{k}^{-t})=f\left((\frac{1}{\omega_k})^t\right)$
• 记 $c=\frac{1}{\omega_k}$，即求所有的 $f(c^i)$，用上一题的做法即可

题目：TopCoder 11351 TheCowDivOne

解答：

• $Ans=\sum_{i}[n\mid i][x^i][y^k]\prod_{j=0}^{n-1}(1+x^jy)$
• $Ans=\sum_{i}\frac{1}{n}\sum_{t=0}^{n-1}\omega_n^{ti}[x^i][y^k]\prod_{j=0}^{n-1}(1+x^jy)$
• $Ans=\frac{1}{n}\sum_{t=0}^{n-1}[y^k]\prod_{j=0}^{n-1}(1+\omega_n^{tj}y)$
• 设 $d=\gcd(t,n)$，$Ans=\frac{1}{n}\sum_{t=0}^{n-1}[y^k]\left(\prod_{i=0}^{\frac{n}{d}-1}\left(1+\omega_{\frac{n}{d}}^iy\right)\right)^d$
• 我们知道 $x^n-1=\prod_{i=0}^{n-1} (x-\omega_n^i)$，代入 $x=-\frac{1}{y}$，得 $(-\frac{1}{y})^n-1=\prod_{i=0}^{n-1} (-\frac{1}{y}-\omega_n^i)\Rightarrow\prod_{i=0}^{n-1} (1+\omega_n^iy)=1-(-y)^n$
• $Ans=\frac{1}{n}\sum_{d\mid n}\varphi(\frac{n}{d})[y^k]\left(1-(-y)^{\frac{n}{d}}\right)^d$
• $Ans=\frac{1}{n}\sum_{d\mid n}\varphi(d)[y^k]\left(1-(-y)^{d}\right)^\frac{n}{d}$，可以看出，当 $d\mid k$ 时才有贡献
• $Ans=\frac{1}{n}\sum_{d\mid n,k}\varphi(d)[y^{\frac{k}{d}}]\left(1+(-1)^{d+1}y\right)^\frac{n}{d}$
• $Ans=\frac{1}{n}\sum_{d\mid n,k}\varphi(d)\dbinom{\frac{n}{d}}{\frac{k}{d}}(-1)^{(d+1)\frac{k}{d}}$，发现 $k$ 较小，可做

题目：HT-054-NOI 优秀的匹配

解答：

• 不易想到，行列式的完全展开式里自带枚举排列
• 构造矩阵 $A$，当 $a_{i,j}=-1$ 时，$A_{i,j}=0$，否则 $A_{i,j}=x^{a_{i,j}}$
• 若 $\exist \,k\mid i,[x^i]det(A)\ne 0$，则有解
• 若都等于 0，也可能是正负抵消了，因此将 $A_{i,j}=rand()\times x^{a_{i,j}}$，这样可以避免正负抵消
• 因为加了随机化，事实上，求 $Ans=\sum_{k\mid i} [x^i]det(A)$ 是否为 0 即可
• 单位根反演，$Ans=\frac{1}{k}\sum_{i=0}^{k-1} f(\omega_k^i)$，其中 $f(x)$ 就是 $det(A)$ 对应的多项式
• 将每个 $\omega_k^i$ 代入算行列式即可

总结：何时用单位根反演：

• $k\mid mod-1$，$mod$ 为质数，有模 $mod$ 的原根
• $[k\mid i]$
• $i \equiv x \pmod{k} \Rightarrow [k\mid i-x]$
• $\lfloor \frac{i}{k} \rfloor$，枚举 $j=i\bmod k$，变为 $\frac{i-j}{k}$
• $\sum_i f(ki+x)$，可化为 $\sum_j f(j) [j\equiv x \pmod{k} ]$
• 求和为 $k$ 的倍数的方案数