bzoj4816 [SDOI2017]数字表格 [莫比乌斯反演]

题目

Luogu 3704
Bzoj 4816

其中 $f[i]$ 为 $Fibonacci$ 数列的第 $i$ 项。答案对 $10^9 + 7$ 取模。

分析

首先肯定是要写暴力(要把自己摘出来 - $from \ Tril$),假定 $n \leqslant m$

把 $Fibonacci$ 数列打出来,记 $times[d]$ 表示满足 $[gcd(i, j)] = d$ 的 $(i, j)$ 的对数,然后就有

然后就有 $60$ 分了,不想写正解了快溜,复杂度 $O(T n log log n)$

看到 $gcd$ 就想到莫比乌斯反演,令 $gcd(i, j) = d$ 推式子

提出次数,反演

令 $T = dg$

$\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor$ 可以数论分块了,提出来,带回原式

令 $F(T) = \prod_{d|T} f[d]^{\mu(\frac{T}{d})}$

然后如果可以预处理 $F(T)$,那么直接数论分块就可以了。

预处理可以直接刷表,枚举 $d$ 和 $d$ 的倍数,$O(n log log n)$ 预处理即可。

复杂度应该没有问题吧

代码

这个是 $60$ 分的暴力,空格好哇

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
#include <bits/stdc++.h>
using namespace std;

namespace TYC
{
typedef long long ll;
const int N = 1e6 + 10;
const int p = 1e9 + 7;
const int Phi = 1e9 + 6;

int f[N], times[N];

inline int read()
{
int x = 0;
char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch))
x = x * 10 + ch - '0', ch = getchar();
return x;
}

#define Mod(x) (x) >= p ? (x) - p : (x)

inline ll qpow(ll x, ll tim)
{
ll ans = 1;
for (; tim; tim >>= 1, x = x * x % p)
if (tim & 1) ans = ans * x % p;
return ans;
}

void work()
{
f[0] = 0, f[1] = 1;
for (int i = 2; i <= 1000000; i++)
f[i] = Mod(f[i - 1] + f[i - 2]);
int T = read();
while (T--)
{
int n = read(), m = read(), mn = min(n, m);
memset(times, 0, sizeof(int[mn + 1]));
for (int i = mn; i; i--)
{
times[i] = (ll)(n / i) * (m / i) % Phi;
for (int j = i + i; j <= mn; j += i)
times[i] = (times[i] - times[j] + Phi) % Phi;
}
ll ans = 1LL;
for (int i = 1; i <= mn; i++)
ans = ans * qpow(f[i], times[i])% p;
printf("%lld\n", ans);
}
}
}

int main()
{
TYC::work();
return 0;
}

Accepted

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;

namespace TYC
{
typedef long long ll;
const int N = 1e6;
const int p = 1e9 + 7;

int f[N + 5], F[N + 5], mu[N + 5];

inline int read()
{
int x = 0;
char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch))
x = x * 10 + ch - '0', ch = getchar();
return x;
}

#define Mod(x) (x) >= p ? (x) - p : (x)

inline ll qpow(ll x, ll tim)
{
if (tim < 0) tim += p - 1;
ll ans = 1;
for (; tim; tim >>= 1, x = x * x % p)
if (tim & 1) ans = ans * x % p;
return ans;
}

void get_mu()
{
static int cnt, prime[N], vis[N + 5];
mu[1] = 1;
for (int i = 2; i <= N; i++)
{
if (!vis[i])
prime[++cnt] = i, mu[i] = -1;
for (int j = 1, k; j <= cnt && (k = i * prime[j]) <= N; j++)
{
vis[k] = 1;
if (i % prime[j] == 0) break;
mu[k] = -mu[i];
}
}
}

void init()
{
f[0] = 0, f[1] = 1;
for (int i = 2; i <= N; i++)
f[i] = Mod(f[i - 1] + f[i - 2]);
get_mu();
static int arr[3];
for (int i = 0; i <= N; i++) F[i] = 1;
for (int i = 1; i <= N; i++)
{
arr[0] = qpow(f[i], -1);
arr[2] = f[i];
for (int j = i; j <= N; j += i)
if (mu[j / i]) F[j] = (ll)F[j] * arr[mu[j / i] + 1] % p;
}
for (int i = 2; i <= N; i++)
F[i] = (ll)F[i - 1] * F[i] % p;
}

void work()
{
init();
int T = read();
while (T--)
{
int n = read(), m = read();
if(n > m) swap(n, m);
ll ans = 1;
for (int l = 1, r; l <= n; l = r + 1)
{
r = min(n / (n / l), m / (m / l));
ll inv = qpow(F[l - 1], p - 2);
ans = ans * qpow(F[r] * inv % p, (ll)(n / l) * (m / l) % (p - 1)) % p;
}
printf("%lld\n", ans);
}
}
}

int main()
{
TYC::work();
return 0;
}