单位根反演学习笔记

恒等式

\[ [d|n]=\frac{1}{d} \sum_{i=0}^{d-1} \omega_d^{i\times n} \]

其中 \(\omega_d\)\(d\) 次单位根

  • \(d|n\),右边和式中每一项都为 \(1\)

  • \(d\nmid n\),容易得到右边为 \(0\)

例题

PYXFIB

BZOJ 3328: PYXFIB

题意

令数列 \(f_0=f_1=1,f_n=f_{n-1}+f_{n-2}\)

给出 \(n,k,p\)

\[ \sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{n}{i\times k}\times f_{i\times k} \]

模质数 \(p\) 的值,且 \(p \equiv 1 \pmod{k}\)

不超过 \(20\) 组数据

\(n\le 10^{18}, p\le 10^9, k\le 20000\)

做法

所求转化为

\[ \sum_{i=0}^n [k|i] \binom{n}{i}\times f_{i} \]

考虑用递推矩阵代替 \(f\) 数列

\[ A= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \]

所求即为

\[ \sum_{i=0}^n [k|i] \binom{n}{i}\times A^i \]

第一行第一列的元素

把恒等式代入得到

\[ \begin{aligned} & \frac{1}{k}\sum_{i=0}^n \binom{n}{i}\times A^i \sum_{j=0}^{k-1} \omega_k^{i\times j} \\ = & \frac{1}{k} \sum_{j=0}^{k-1} \sum_{i=1}^n \binom{n}{i}\times A^i \times \omega_{k}^{i\times j} \\ = & \frac{1}{k} \sum_{j=0}^{k-1}\left(\omega_k^jA+I \right)^n \end{aligned} \]

最后一步用了二项式定理,其中 \(I=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\)

由于保证了 \(p \equiv 1 \pmod{k}\),直接在模意义下计算 \(\omega_k\) 即可

复杂度 \(\mathcal O(k\log n)\)

代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>

using namespace std;
#define ll long long

int k, p, T;
ll n;
struct matrix{
int f[2][2];
inline matrix(){}
inline matrix(int a, int b, int c, int d){ f[0][0]=a, f[0][1]=b, f[1][0]=c, f[1][1]=d;}
inline matrix operator +(const matrix &rhs)const{
return matrix(
(f[0][0]+rhs.f[0][0])%p,
(f[0][1]+rhs.f[0][1])%p,
(f[1][0]+rhs.f[1][0])%p,
(f[1][1]+rhs.f[1][1])%p
);
}
inline matrix operator *(const int rhs)const{
return matrix(
(ll)f[0][0]*rhs%p,
(ll)f[0][1]*rhs%p,
(ll)f[1][0]*rhs%p,
(ll)f[1][1]*rhs%p
);
}
inline matrix operator *(const matrix &rhs)const{
return matrix(
((ll)f[0][0]*rhs.f[0][0]+(ll)f[0][1]*rhs.f[1][0])%p,
((ll)f[0][0]*rhs.f[0][1]+(ll)f[0][1]*rhs.f[1][1])%p,
((ll)f[1][0]*rhs.f[0][0]+(ll)f[1][1]*rhs.f[1][0])%p,
((ll)f[1][0]*rhs.f[0][1]+(ll)f[1][1]*rhs.f[1][1])%p
);
}
} A=matrix(1, 1, 1, 0), I=matrix(1, 0, 0, 1);
inline int Pow(ll x, int y=p-2){
int ans=1;
for(; y; y>>=1, x=x*x%p) if(y&1) ans=ans*x%p;
return ans;
}
inline matrix Pow(matrix x, ll y){
matrix ans=I;
for(; y; y>>=1, x=x*x) if(y&1) ans=ans*x;
return ans;
}
inline int getroot(int p){
vector<int> d;
for(int i=2, x=p-1; i*i<=x; ++i) if(x%i==0){
d.push_back(p/i), x/=i;
while(x%i==0) x/=i;
}
for(int i=2; i<p; ++i){
for(unsigned j=0; j<d.size(); ++j) if(Pow(i, d[j])==1) goto nxt;
return i;
nxt:;
}
}
int main() {
scanf("%d", &T);
while(T--){
scanf("%lld%d%d", &n, &k, &p);
int w=Pow(getroot(p), (p-1)/k);
ll ans=0;
for(int i=0, now=1; i<k; now=(ll)now*w%p, ++i) ans+=Pow(A*now+I, n).f[0][0];
printf("%lld\n", ans%p*Pow(k)%p);
}
return 0;
}

LJJ 学二项式定理

LOJ #6485. LJJ 学二项式定理

题意

\(T\) 组数据,给出 \(n,s,a_0,a_1,a_2,a_3\)

\[ \left(\sum_{i=0}^n \binom{n}{i}\times s^i\times a_{i\bmod 4}\right) \bmod 998244353 \]

\(T\le 10^5,n\le 10^{18}\)

\(s,a_0,a_1,a_2,a_3\le 10^8\)

做法

考虑计算 \(i\)\(4\) 的倍数情况

\[ \begin{aligned} & \sum_{i=0}^n [4|i] \binom{n}{i}\times s^i\times a_0 \\ = & \frac{1}{4} \sum_{i=0}^n \binom{n}{i}\times s^i\times a_0 \sum_{j=0}^3 \omega_4^{i\times j} \\ = & \frac{a_0}{4}\sum_{j=0}^3 \sum_{i=0}^n \omega_4^{i\times j} \times \binom{n}{i}\times s^i \\ = & \frac{a_0}{4}\sum_{j=0}^3 (\omega_4^j\times s +1)^n \end{aligned} \]

其他 \(3\) 种情况也类似,以 \(i\equiv 1\pmod 4\) 为例

\[ \begin{aligned} & \sum_{i=0}^n [4|(i-1)] \binom{n}{i}\times s^i\times a_1 \\ = & \frac{1}{4} \sum_{i=0}^n \binom{n}{i}\times s^i\times a_1 \sum_{j=0}^3 \omega_4^{(i-1)\times j} \\ = & \frac{a_1}{4}\sum_{j=0}^3 \sum_{i=0}^n \omega_4^{(i-1)\times j} \times \binom{n}{i}\times s^i \\ = & \frac{a_1}{4}\sum_{j=0}^3 \omega_4^{-j} (\omega_4^j\times s +1)^n \end{aligned} \]

复杂度 \(\mathcal O(\log n)\)

代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>

using namespace std;
#define ll long long

inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig=false, c=read(); !isdigit(c); c=read()) {
if (c == '-') iosig=true;
if (c == -1) return;
}
for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
*ooh++=c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x==0) print('0');
else {
if (x<0) print('-'), x=-x;
for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
while(cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int P = 998244353, w4 = 911660635, i4 = 748683265;
int T, s, a[4];
ll n;
inline int Pow(ll x, int y=P-2){
int ans=1;
for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
return ans;
}
int main() {
read(T);
while(T--){
read(n), read(s), read(a[0]), read(a[1]), read(a[2]), read(a[3]), n%=P-1;
int ans=0;
for(int j=0, w=1, iw=1; j<4; ++j, w=(ll)w*w4%P, iw=(ll)iw*(P-w4)%P){
int t=Pow((ll)s*w%P+1, n);
for(int i=0, ww=1; i<4; ++i, ww=(ll)ww*iw%P) ans=(ans+(ll)t*ww%P*a[i])%P;
}
print((int)((ll)i4*ans%P)), print('\n');
}
return flush(), 0;
}

复读机

UOJ #450. 【集训队作业2018】复读机

题意

\(k\) 个不同的复读机,接下来 \(n\) 秒中每秒都会挑一个复读机复读,一个复读机复读了 \(d\) 的倍数次才会感到快乐

求有多少种方案使得所有复读机都感到快乐,模 \(19491001\)

三种子任务

  1. \(k\le 500000,d=1\)
  2. \(k\le 500000,d=2\)
  3. \(k\le 1000,d=3\)

\(n\le 10^9\)

做法

\(d=1\) 时,答案即为 \(k^n\)

\(d>1\) 时考虑 dp

\(f_{i,j}\) 表示 \(i\) 个复读机,一共复读了 \(j\) 次的方案数(方案不同当且仅当存在第 \(x\) 次复读的复读机不同)

于是

\[ \begin{aligned} f_{i,j} & = \sum_{x=0}^{j} [d|x] f_{i-1,j-x}\binom{j}{x} \\ & = \frac{1}{d} \sum_{x=0}^j f_{i-1,j-x} \binom{j}{x} \sum_{t=0}^{d-1} \omega_d^{tx} \\ \frac{f_{i,j}}{j!} &= \frac{1}{d} \sum_{x=0}^j \frac{f_{i-1,j-x}}{(j-x)!} \times \frac{\sum_{t=0}^{d-1} \omega_d^{tx}}{x!} \end{aligned} \]

用生成函数表示第二维的转移即

\[ \begin{aligned} f_i(x) & = \sum_{j=0}^{\infty} f_{i,j}x^j \\ f_i(x) & = f_{i-1}(x)\times \left(\frac{\sum_{j=0}^{\infty} \sum_{t=0}^{d-1} \frac{\omega_d^{tj}}{j!}x^j }{d}\right) \\ f_k(x) & = \left(\frac{\sum_{j=0}^{\infty} \sum_{t=0}^{d-1} \frac{\omega_d^{tj}}{j!}x^j }{d}\right) ^k \\ & = \left(\frac{\sum_{t=0}^{d-1} \sum_{j=0}^{\infty} \frac{\omega_d^{tj}}{j!}x^j }{d}\right) ^k \end{aligned} \]

\(d=2\) 时,展开 \(t\) 的枚举,得到

\[ \left(\sum_{j=0}^{\infty} \frac{x^j}{j!}\right)+\left(\sum_{j=0}^{\infty} \frac{\omega_2^j x^j}{j!}\right) = e^x+e^{\omega_2x} \]

其中 \(\omega_2=-1\)

所求

\[ \begin{aligned} f_{k,n} & = n![x^n]f_k(x) \\ & = n![x^n]\left(\frac{e^x+e^{-x}}{2}\right)^k \\ & = \frac{n![x^n]\left(\sum_{i=0}^k e^{ix} \times e^{-(k-i)x}\times \binom{k}{i}\right)}{2^k} \end{aligned} \]

复杂度 \(\mathcal O(k\log n)\)

\(d=3\) 同理,展开

\[ \left( \frac{e^x+e^{\omega_3 x}+e^{\omega_3^2 x}}{3}\right)^k \]

枚举其中两项,复杂度 \(\mathcal O(k^2\log n)\)

代码

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
#include<cstdio>

using namespace std;
#define ll long long

const int N = 500005, P = 19491001, w = 18827933, ww = (ll)w*w%P, inv2 = (P+1)/2, inv3 = (P*2+1)/3;
int n, k, d, ans, fac[N], ifac[N];
inline int Pow(ll x, int y=P-2){
int ans=1;
for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
return ans;
}
int main() {
scanf("%d%d%d", &n, &k, &d);
if(d==1) printf("%d", Pow(k, n));
else{
fac[0]=1;
for(int i=1; i<=k; ++i) fac[i]=(ll)fac[i-1]*i%P;
ifac[k]=Pow(fac[k]);
for(int i=k; i; --i) ifac[i-1]=(ll)ifac[i]*i%P;
if(d==2){
for(int i=0; i<=k; ++i) ans=(ans+(ll)Pow(i*2-k+P, n)*ifac[i]%P*ifac[k-i])%P;
printf("%lld", (ll)ans*fac[k]%P*Pow(inv2, k)%P);
}
else{
for(int i=0; i<=k; ++i) for(int j=0; i+j<=k; ++j)
ans=(ans+(ll)Pow((i+(ll)j*w+(ll)(k-i-j)*ww)%P, n)*ifac[i]%P*ifac[j]%P*ifac[k-i-j])%P;
printf("%lld", (ll)ans*fac[k]%P*Pow(inv3, k)%P);
}
}
return 0;
}

倍数?倍数!

BZOJ 4314: 倍数?倍数!

题意

求从 \(0,1,\dotsc,n-1\) 选出 \(k\) 个互不相同的数和为 \(n\) 的倍数的方案数,模 \(10^9+7\)

\(n\le 10^9, k\le 1000\)

做法

神仙题

膜 YX 大爷

先不考虑 \(k\) 的限制,求从 \(0,1,\dotsc,n-1\) 中选出任意个数和为 \(n\) 的倍数的方案数

考虑生成函数,答案为

\[ f(x) = \prod_{i=0}^{n-1} (x^i+1) = \sum_{i=0}^\infty f_ix^i \]

的所有 \(n\) 的倍数次项系数的和,即

\[ \begin{aligned} & \sum_{i=0}^\infty [n|i]\times f_i \\ = & \frac{1}{n} \sum_{i=0}^\infty f_i \sum_{j=0}^{n-1} \omega_n^{i\times j} \\ = & \frac{1}{n} \sum_{j=0}^{n-1} \sum_{i=0}^\infty f_i(\omega_n^j)^i \\ = & \frac{1}{n} \sum_{j=0}^{n-1} f(\omega_n^j) \\ = & \frac{1}{n} \sum_{j=0}^{n-1} \prod_{i=0}^{n-1} (\omega_n^{i\times j}+1) \end{aligned} \]

枚举 \(g=\gcd(j,n)\),由单位根的性质,上式等于

\[ \begin{aligned} & \frac{1}{n} \sum_{g|n} \sum_{j=0}^{\frac{n}{g} -1} [j \perp \frac{n}{g}] \prod_{i=0}^{n-1} (\omega_{\frac{n}{g}}^{i\times j}+1) \\ = & \frac{1}{n} \sum_{g|n} \sum_{j=0}^{\frac{n}{g} -1} [j \perp \frac{n}{g}] \left( \prod_{i=0}^{\frac{n}{g}-1} (\omega_{\frac{n}{g}}^{i\times j}+1)\right)^g \\ \end{aligned} \]

由于 \(j\)\(\frac{n}{g}\) 互质,上式等于

\[ \begin{aligned} & \frac{1}{n} \sum_{g|n} \sum_{j=0}^{\frac{n}{g} -1} [j \perp \frac{n}{g}] \left( \prod_{i=0}^{\frac{n}{g}-1} (\omega_{\frac{n}{g}}^{i}+1)\right)^g \\ = & \frac{1}{n} \sum_{g|n} \varphi(\frac{n}{g}) \left( \prod_{i=0}^{\frac{n}{g}-1} (\omega_{\frac{n}{g}}^{i}+1)\right)^g \end{aligned} \]

考虑单位根的意义 \(x^n-1=0=\prod_{i=0}^{n-1} (x-\omega_n^i)\)

代入 \(x=-1\) 得到 \((-1)^n-1=(-1)^n \prod_{i=0}^{n-1} (\omega_n^i+1)\)

因此 \(\prod_{i=0}^{n-1} (\omega_n^i+1)=1-(-1)^n\)

答案等于

\[ \frac{1}{n} \sum_{g|n} \varphi(\frac{n}{g}) \left(1-(-1)^{\frac{n}{g}}\right)^g \]

考虑有了选 \(k\) 个的限制

答案为

\[ [y^k]\prod_{i=0}^{n-1} (x^iy+1) \]

的所有 \(n\) 的倍数次项系数的和

大致过程与上面相同,把 \(y\) 保留,在代入时代入 \(-\frac{1}{y}\),最后得到

\[ \frac{1}{n} \sum_{g|n} \varphi(\frac{n}{g}) \left(1-(-y)^{\frac{n}{g}}\right)^g \]

求第 \(k\) 项系数

要对答案有贡献,记 \(d=\frac{n}{g}\)

必须满足 \(d|k\),因此 \(\varphi(d)\) 的部分可以做到 \(\mathcal O(k)\)

另外还要求 \(\binom{g}{\frac{k}{d}}\),单次 \(\mathcal O(\frac{k}{d})\),总复杂度 \(\mathcal O(\sigma_1(k))\approx \mathcal O(k\log \log k)\)

所以 \(k\) 还可以放大一点

代码

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>

using namespace std;
#define ll long long

const int N = 1005, P = 1000000007;
int n, k, ans, cnt, phi[N], prime[N], ifac[N];
bool p[N];
inline int Pow(ll x, int y=P-2){
int ans=1;
for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
return ans;
}
inline int C(int x, int y){
int ans=1;
for(int i=0; i<y; ++i) ans=(ll)ans*(x-i)%P;
return (ll)ans*ifac[y]%P;
}
int main() {
scanf("%d%d", &n, &k);
ifac[0]=1;
for(int i=1; i<=k; ++i) ifac[i]=(ll)ifac[i-1]*i%P;
ifac[k]=Pow(ifac[k]);
for(int i=k; i; --i) ifac[i-1]=(ll)ifac[i]*i%P;
phi[1]=1;
for(int i=2; i<=k; ++i){
if(!p[i]) phi[i]=i-1, prime[++cnt]=i;
for(int j=1; j<=cnt && i*prime[j]<=k; ++j){
p[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
for(int i=1; i<=k; ++i) if(k%i==0 && n%i==0) ans=(ans+(k&1?1ll:(k/i&1?-1ll:1ll))*phi[i]*C(n/i, k/i))%P;
return printf("%lld", (ll)Pow(n)*(ans+P)%P), 0;
}
0%