0%

单位根反演学习笔记

恒等式

$$
[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;
}