杂题小记（2023.03.08）

杂题小记（2023.03.08）更好的阅读体验戳此进入LG-P8348 「Wdoi-6」未知之花魅知之旅LG-P3121 [USACO15FEB]Censoring GLG-P3172 [CQOI2015]选数LG-P3327 [SDOI2015]约数个数和LG-P1829 [国家集训队]Crash的数字表格 / JZPTABCF235E Number ChallengeLG-P4619 [SDOI2018]旧试题LG-P3704 [SDOI2017]数字表格UPD

更好的阅读体验戳此进入

LG-P8348 「Wdoi-6」未知之花魅知之旅

考虑到限制可以转化为两个数相减或相加可以推出下一个数，然后发现相加操作可以被相减操作代替，同时发现多次相减可以合成，最后判一下减到最小的结果是否相同即可。


xxxxxxxxxx
71
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
int main(){
27
    int T = read();
28
    while(T--){
29
        int a = read(), b = read(), x = read(), y = read(), k = read();
30
        auto Cal = [k](int &a, int &b)->void{
31
            while(true){
32
                if(a > b){
33
                    int cnt = (a - k) / b;
34
                    if(!cnt)return;
35
                    if(cnt & 1)a -= cnt * b, swap(a, b);
36
                    else a -= cnt * b;
37
                }else if(a < b){
38
                    int cnt = (b - k) / a;
39
                    if(!cnt)return;
40
                    if(cnt & 1)b -= cnt * a, swap(a, b);
41
                    else b -= cnt * a;
42
                }else return;
43
            }
44
        };
45
        auto Check = [&](void)->bool{
46
            if(a < k || b < k || x < k || y < k)return false;
47
            if(a == x && b == y)return true;
48
            Cal(a, b), Cal(x, y);
49
            return a == x && b == y;
50
        };
51
        printf("%s\n", Check() ? "yes" : "no");
52
    }
53
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54
    return 0;
55
}
56

57
template < typename T >
58
inline T read(void){
59
    T ret(0);
60
    int flag(1);
61
    char c = getchar();
62
    while(c != '-' && !isdigit(c))c = getchar();
63
    if(c == '-')flag = -1, c = getchar();
64
    while(isdigit(c)){
65
        ret *= 10;
66
        ret += int(c - '0');
67
        c = getchar();
68
    }
69
    ret *= flag;
70
    return ret;
71
}

LG-P3121 [USACO15FEB]Censoring G

经典 AC 自动机，维护两个栈记录路径上的指针和答案即可，匹配到时弹出对应数量，并更新 AC 自动机上的指针。


xxxxxxxxxx
99
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define d(c) (c - 'a')
24
#define c(d) (char(d + 'a'))
25

26
template < typename T = int >
27
inline T read(void);
28

29
struct Node{
30
    Node* tr[26];
31
    Node* fail;
32
    int len;
33
    OPNEW;
34
}nd[110000];
35
ROPNEW_NODE;
36
Node* root;
37

38
basic_string < char > ans;
39

40
void Insert(string S){
41
    Node* p = root;
42
    for(auto c : S){
43
        if(!p->tr[d(c)])p->tr[d(c)] = new Node();
44
        p = p->tr[d(c)];
45
    }p->len = S.length();
46
}
47
void Build(void){
48
    queue < Node* > cur;
49
    cur.push(root);
50
    while(!cur.empty()){
51
        auto p = cur.front(); cur.pop();
52
        for(int i = 0; i < 26; ++i)
53
            if(p->tr[i])p->tr[i]->fail = p == root ? root : p->fail->tr[i], cur.push(p->tr[i]);
54
            else p->tr[i] = p == root ? root : p->fail->tr[i];
55
    }
56
}
57
void Accept(string S){
58
    basic_string < Node* > cur;
59
    cur += root;
60
    Node* p = root;
61
    for(auto c : S){
62
        p = p->tr[d(c)];
63
        ans += c, cur += p;
64
        if(p->len){
65
            for(int i = 1; i <= p->len; ++i)ans.pop_back(), cur.pop_back();
66
            p = cur.back();
67
        }
68
    }
69
}
70

71
string pat, txt;
72

73
int main(){
74
    root = new Node();
75
    cin >> txt;
76
    int N = read();
77
    while(N--)cin >> pat, Insert(pat);
78
    Build(), Accept(txt);
79
    for(auto c : ans)printf("%c", c);
80
    printf("\n");
81
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
82
    return 0;
83
}
84

85
template < typename T >
86
inline T read(void){
87
    T ret(0);
88
    int flag(1);
89
    char c = getchar();
90
    while(c != '-' && !isdigit(c))c = getchar();
91
    if(c == '-')flag = -1, c = getchar();
92
    while(isdigit(c)){
93
        ret *= 10;
94
        ret += int(c - '0');
95
        c = getchar();
96
    }
97
    ret *= flag;
98
    return ret;
99
}

LG-P3172 [CQOI2015]选数

$dp(i)$ $\gcd = i$ $v^n - v$ $v$ $i$ $dp(i)$ $dp(i \times 2), dp(i \times 3) \cdots$ $dp(1) + 1$ 。


xxxxxxxxxx
71
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MOD (ll)(1e9 + 7)
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N, K, L, H;
29
ll dp[110000];
30

31
ll qpow(ll a, ll b){
32
    ll ret(1), mul(a);
33
    while(b){
34
        if(b & 1)ret = ret * mul % MOD;
35
        b >>= 1;
36
        mul = mul * mul % MOD;
37
    }return ret;
38
}
39

40
int main(){
41
    N = read(), K = read(), L = read(), H = read();
42
    L = (int)ceil((double)L / K), H = H / K;
43
    auto F = [=](int val)->ll{
44
        int l = (int)ceil((double)L / val), r = H / val;
45
        if(l > r)return 0;
46
        return ((qpow(r - l + 1, N) - (r - l + 1)) % MOD + MOD) % MOD;
47
    };
48
    for(int i = H - L; i >= 1; --i){
49
        dp[i] = F(i);
50
        for(int j = i + i; j <= H - L; j += i)
51
            dp[i] = (dp[i] - dp[j] + MOD) % MOD;
52
    }printf("%lld\n", dp[1] + (L == 1));
53
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54
    return 0;
55
}
56

57
template < typename T >
58
inline T read(void){
59
    T ret(0);
60
    int flag(1);
61
    char c = getchar();
62
    while(c != '-' && !isdigit(c))c = getchar();
63
    if(c == '-')flag = -1, c = getchar();
64
    while(isdigit(c)){
65
        ret *= 10;
66
        ret += int(c - '0');
67
        c = getchar();
68
    }
69
    ret *= flag;
70
    return ret;
71
}

LG-P3327 [SDOI2015]约数个数和

主要用到了公式：

d (i j) = \sum_{x | i} \sum_{y | j} [gcd (x, y) = 1]

后面的部分就是标准的莫反后数论分块了。


xxxxxxxxxx
83
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define LIM (51000)
24

25
template < typename T = int >
26
inline T read(void);
27

28
ll F[LIM + 100];
29
ll mu[LIM + 100], smu[LIM + 100];
30
bitset < LIM + 100 > notPrime;
31
basic_string < int > Prime;
32

33
int main(){mu[1] = 1;
34
    for(int i = 2; i <= LIM; ++i){
35
        if(!notPrime[i])Prime += i, mu[i] = -1;
36
        for(auto p : Prime){
37
            if((ll)i * p > LIM)break;
38
            mu[i * p] = i % p == 0 ? 0 : mu[i] * mu[p];
39
            notPrime[i * p] = true;
40
            if(i % p == 0)break;
41
        }
42
    }
43
    for(int i = 1; i <= LIM; ++i)smu[i] = smu[i - 1] + mu[i];
44
    for(int i = 1; i <= LIM; ++i){
45
        int l = 1;
46
        while(l <= i){
47
            int r = i / (i / l);
48
            F[i] += i / l * (r - l + 1);
49
            l = r + 1;
50
        }
51
    }
52
    int T = read();
53
    while(T--){
54
        ll ans(0);
55
        int N = read(), M = read();
56
        int lim = min(N, M);
57
        int l = 1;
58
        while(l <= lim){
59
            int r = min(N / (N / l), M / (M / l));
60
            ans += (smu[r] - smu[l - 1]) * F[N / l] * F[M / l];
61
            l = r + 1;
62
        }printf("%lld\n", ans);
63
    }
64

65
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
66
    return 0;
67
}
68

69
template < typename T >
70
inline T read(void){
71
    T ret(0);
72
    int flag(1);
73
    char c = getchar();
74
    while(c != '-' && !isdigit(c))c = getchar();
75
    if(c == '-')flag = -1, c = getchar();
76
    while(isdigit(c)){
77
        ret *= 10;
78
        ret += int(c - '0');
79
        c = getchar();
80
    }
81
    ret *= flag;
82
    return ret;
83
}

LG-P1829 [国家集训队]Crash的数字表格 / JZPTAB

标准莫反，没什么特别的，注意细节即可。


xxxxxxxxxx
92
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define LIM (11000000)
24
#define MOD (20101009)
25

26
template < typename T = int >
27
inline T read(void);
28

29
int N, M;
30
// ll F[LIM + 100];
31
ll mu[LIM + 100], smu[LIM + 100];
32
bitset < LIM + 100 > notPrime;
33
basic_string < int > Prime;
34

35
ll qpow(ll a, ll b){
36
    ll ret(1), mul(a);
37
    while(b){
38
        if(b & 1)ret = ret * mul % MOD;
39
        b >>= 1;
40
        mul = mul * mul % MOD;
41
    }return ret;
42
}
43

44
int main(){mu[1] = 1;
45
    for(int i = 2; i <= LIM; ++i){
46
        if(!notPrime[i])Prime += i, mu[i] = -1;
47
        for(auto p : Prime){
48
            if((ll)i * p > LIM)break;
49
            mu[i * p] = i % p == 0 ? 0 : mu[i] * mu[p];
50
            notPrime[i * p] = true;
51
            if(i % p == 0)break;
52
        }
53
    }
54
    for(int i = 1; i <= LIM; ++i)smu[i] = ((smu[i - 1] + mu[i] * i % MOD * i % MOD) % MOD + MOD) % MOD;
55
    ll inv2 = qpow(2, MOD - 2);
56
    auto CalF = [inv2](ll n, ll m)->ll{
57
        return (n * (n + 1) / 2) % MOD * ((m * (m + 1) / 2) % MOD) % MOD;
58
    };
59
    ll ans(0);
60
    N = read(), M = read();
61
    int lim = min(N, M);
62
    int l = 1;
63
    while(l <= lim){
64
        int r = min(N / (N / l), M / (M / l));
65
        int cn = N / l, cm = M / l;
66
        int clim = min(cn, cm);
67
        int cl = 1;
68
        while(cl <= clim){
69
            int cr = min(cn / (cn / cl), cm / (cm / cl));
70
            (ans += ((ll)(r + l) * (r - l + 1) / 2 % MOD) * (smu[cr] - smu[cl - 1] + MOD) % MOD * CalF(cn / cl, cm / cl) % MOD) %= MOD;
71
            cl = cr + 1;
72
        }l = r + 1;
73
    }printf("%lld\n", ans);
74
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
75
    return 0;
76
}
77

78
template < typename T >
79
inline T read(void){
80
    T ret(0);
81
    int flag(1);
82
    char c = getchar();
83
    while(c != '-' && !isdigit(c))c = getchar();
84
    if(c == '-')flag = -1, c = getchar();
85
    while(isdigit(c)){
86
        ret *= 10;
87
        ret += int(c - '0');
88
        c = getchar();
89
    }
90
    ret *= flag;
91
    return ret;
92
}

CF235E Number Challenge

感觉莫反的题都没什么可说的，基本上就是各种推导的套路然后各种预处理即可。


xxxxxxxxxx
85
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define LIM (2100)
24
#define MOD (ll)(1073741824)
25

26
template < typename T = int >
27
inline T read(void);
28

29
int A, B, C;
30
ll ans(0);
31
ll mu[LIM + 100], smu[LIM + 100];
32
ll G[LIM + 100][LIM + 100];
33
bitset < LIM + 100 > notPrime;
34
basic_string < int > Prime;
35

36
ll qpow(ll a, ll b){
37
    ll ret(1), mul(a);
38
    while(b){
39
        if(b & 1)ret = ret * mul % MOD;
40
        b >>= 1;
41
        mul = mul * mul % MOD;
42
    }return ret;
43
}
44

45
int main(){mu[1] = 1;
46
    for(int i = 2; i <= LIM; ++i){
47
        if(!notPrime[i])Prime += i, mu[i] = -1;
48
        for(auto p : Prime){
49
            if((ll)i * p > LIM)break;
50
            mu[i * p] = i % p == 0 ? 0 : mu[i] * mu[p];
51
            notPrime[i * p] = true;
52
            if(i % p == 0)break;
53
        }
54
    }
55
    for(int x = 1; x <= LIM; ++x)for(int i = 1; i <= LIM; ++i){
56
        if(__gcd(x, i) != 1)continue;
57
        for(int y = i; y <= LIM; y += i)(++G[x][y]) %= MOD;
58
    }
59
    for(int x = 1; x <= LIM; ++x)for(int y = 1; y <= LIM; ++y)(G[x][y] += G[x][y - 1]) %= MOD;
60
    A = read(), B = read(), C = read();
61
    for(int x = 1; x <= A; ++x)
62
        for(int d = 1; d <= min(B, C); ++d){
63
            if(__gcd(x, d) != 1)continue;
64
            (ans += A / x * mu[d] % MOD * G[x][B / d] % MOD * G[x][C / d] % MOD) %= MOD;
65
        }
66
    printf("%lld\n", ans);
67
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
68
    return 0;
69
}
70

71
template < typename T >
72
inline T read(void){
73
    T ret(0);
74
    int flag(1);
75
    char c = getchar();
76
    while(c != '-' && !isdigit(c))c = getchar();
77
    if(c == '-')flag = -1, c = getchar();
78
    while(isdigit(c)){
79
        ret *= 10;
80
        ret += int(c - '0');
81
        c = getchar();
82
    }
83
    ret *= flag;
84
    return ret;
85
}

LG-P4619 [SDOI2018]旧试题

莫反推式子 + 三元环优化，巨恶心，但是思路还是比较清晰明了的，同时不知道为什么我的程序跑的飞快。。。


xxxxxxxxxx
138
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define LIM (110000)
24
#define MOD (ll)(1e9 + 7)
25

26
template < typename T = int >
27
inline T read(void);
28

29
int A, B, C;
30
ll mu[LIM + 100], smu[LIM + 100];
31
ll fa[LIM + 100], fb[LIM + 100], fc[LIM + 100];
32
int val[LIM + 100];
33
int deg[LIM + 100];
34
bitset < LIM + 100 > vis;
35
bitset < LIM + 100 > notPrime;
36
basic_string < int > Prime;
37

38
struct Edge{
39
    Edge* nxt;
40
    int to;
41
    int val;
42
    OPNEW;
43
}ed[LIM << 5];
44
ROPNEW;
45
Edge* head[LIM];
46

47
ll qpow(ll a, ll b){
48
    ll ret(1), mul(a);
49
    while(b){
50
        if(b & 1)ret = ret * mul % MOD;
51
        b >>= 1;
52
        mul = mul * mul % MOD;
53
    }return ret;
54
}
55

56
int main(){mu[1] = 1;
57
    for(int i = 2; i <= LIM; ++i){
58
        if(!notPrime[i])Prime += i, mu[i] = -1;
59
        for(auto p : Prime){
60
            if((ll)i * p > LIM)break;
61
            mu[i * p] = i % p == 0 ? 0 : mu[i] * mu[p];
62
            notPrime[i * p] = true;
63
            if(i % p == 0)break;
64
        }
65
    }
66
    int T = read();
67
    while(T--){
68
        ll ans(0);
69
        A = read(), B = read(), C = read();
70
        int mn = min({A, B, C}), mx = max({A, B, C});
71
        memset(fa, 0, sizeof fa), memset(fb, 0, sizeof fb), memset(fc, 0, sizeof fc);
72
        memset(deg, 0, sizeof deg), memset(head, 0, sizeof head);
73
        for(int i = 1; i <= A; ++i)
74
            for(int j = i; j <= mx; j += i)(fa[i] += A / j) %= MOD;
75
        for(int i = 1; i <= B; ++i)
76
            for(int j = i; j <= mx; j += i)(fb[i] += B / j) %= MOD;
77
        for(int i = 1; i <= C; ++i)
78
            for(int j = i; j <= mx; j += i)(fc[i] += C / j) %= MOD;
79
        for(int i = 1; i <= mn; ++i)(ans += fa[i] * fb[i] * fc[i] * mu[i] * mu[i] * mu[i]) %= MOD;
80
        struct Edg{int s, t, v;}; basic_string < Edg > edgs;
81
        for(int g = 1; g <= mn; ++g){
82
            for(int i = 1; (ll)i * g <= mx; ++i){
83
                if(!mu[i * g])continue;
84
                for(int j = i + 1; (ll)i * j * g <= mx; ++j){
85
                    if(!mu[j * g] || __gcd(i, j) != 1)continue;
86
                    int s = i * g, t = j * g, lcm = i * j * g;
87
                    (ans += ((mu[s] * mu[s] * mu[t] * ((fa[s] * fb[lcm] * fc[lcm] + fa[lcm] * fb[s] * fc[lcm] + fa[lcm] * fb[lcm] * fc[s]) % MOD)) + MOD) % MOD) %= MOD;
88
                    (ans += ((mu[s] * mu[t] * mu[t] * ((fa[t] * fb[lcm] * fc[lcm] + fa[lcm] * fb[t] * fc[lcm] + fa[lcm] * fb[lcm] * fc[t]) % MOD)) + MOD) % MOD) %= MOD;
89
                    ++deg[s], ++deg[t];
90
                    edgs += {s, t, lcm};
91
                    // head[s] = new Edge{head[s], t, lcm};
92
                    // head[t] = new Edge{head[t], s, lcm};
93
                }
94
            }
95
        }
96
        for(auto edg : edgs){
97
            auto [s, t, v] = edg;
98
            if(deg[s] < deg[t] || (deg[s] == deg[t] && s > t))swap(s, t);
99
            head[s] = new Edge{head[s], t, v};
100
        }
101
        for(int s = 1; s <= mx; ++s){
102
            if(!mu[s])continue;
103
            // vis.reset();
104
            // memset(val, 0, sizeof val);
105
            for(auto i = head[s]; i; i = i->nxt)vis[SON] = true, val[SON] = i->val;
106
            for(auto i = head[s]; i; i = i->nxt){
107
                if(!mu[SON])continue;
108
                for(auto j = head[SON]; j; j = j->nxt){
109
                    if(!vis[j->to] || !mu[j->to])continue;
110
                    (ans += mu[s] * mu[SON] * mu[j->to] * (
111
                        fa[val[j->to]] * fb[j->val] * fc[i->val] + fa[val[j->to]] * fb[i->val] * fc[j->val] +
112
                        fa[j->val] * fb[val[j->to]] * fc[i->val] + fa[j->val] * fb[i->val] * fc[val[j->to]] +
113
                        fa[i->val] * fb[val[j->to]] * fc[j->val] + fa[i->val] * fb[j->val] * fc[val[j->to]]
114
                    ) % MOD) %= MOD;
115
                }
116
            }
117
            for(auto i = head[s]; i; i = i->nxt)vis[SON] = false, val[SON] = 0;
118
        }printf("%lld\n", (ans % MOD + MOD) % MOD);
119
    }
120
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
121
    return 0;
122
}
123

124
template < typename T >
125
inline T read(void){
126
    T ret(0);
127
    int flag(1);
128
    char c = getchar();
129
    while(c != '-' && !isdigit(c))c = getchar();
130
    if(c == '-')flag = -1, c = getchar();
131
    while(isdigit(c)){
132
        ret *= 10;
133
        ret += int(c - '0');
134
        c = getchar();
135
    }
136
    ret *= flag;
137
    return ret;
138
}

LG-P3704 [SDOI2017]数字表格

依然还是莫反然后推式子，不想帖式子，好像也就没什么可写的了。。。


xxxxxxxxxx
95
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define LIM (1100000)
24
#define MOD (ll)(1e9 + 7)
25

26
template < typename T = int >
27
inline T read(void);
28

29
int N, M;
30
ll ans(0);
31
ll mu[LIM + 100], smu[LIM + 100];
32
ll F[LIM + 100], invF[LIM + 100];
33
ll G[LIM + 100], mulG[LIM + 100], invmulG[LIM + 100];
34
bitset < LIM + 100 > notPrime;
35
basic_string < int > Prime;
36

37
ll qpow(ll a, ll b){
38
    ll ret(1), mul(a);
39
    while(b){
40
        if(b & 1)ret = ret * mul % MOD;
41
        b >>= 1;
42
        mul = mul * mul % MOD;
43
    }return ret;
44
}
45

46
int main(){mu[1] = 1;
47
    for(int i = 2; i <= LIM; ++i){
48
        if(!notPrime[i])Prime += i, mu[i] = -1;
49
        for(auto p : Prime){
50
            if((ll)i * p > LIM)break;
51
            mu[i * p] = i % p == 0 ? 0 : mu[i] * mu[p];
52
            notPrime[i * p] = true;
53
            if(i % p == 0)break;
54
        }
55
    }
56
    F[0] = 0, F[1] = 1;
57
    for(int i = 2; i <= LIM; ++i)F[i] = (F[i - 1] + F[i - 2]) % MOD;
58
    for(int i = 1; i <= LIM; ++i)invF[i] = qpow(F[i], MOD - 2);
59
    for(int i = 0; i <= LIM; ++i)G[i] = 1;
60
    for(int i = 1; i <= LIM; ++i)
61
        for(int j = i; j <= LIM; j += i)
62
            (G[j] *= mu[j / i] == 1 ? F[i] : (mu[j / i] == 0 ? 1 : invF[i])) %= MOD;
63
    mulG[0] = invmulG[0] = 1;
64
    for(int i = 1; i <= LIM; ++i)mulG[i] = mulG[i - 1] * G[i] % MOD, invmulG[i] = qpow(mulG[i], MOD - 2);
65
    int T = read();
66
    while(T--){
67
        ans = 1;
68
        N = read(), M = read();
69
        int lim = min(N, M);
70
        int l = 1;
71
        while(l <= lim){
72
            int r = min(N / (N / l), M / (M / l));
73
            (ans *= qpow(mulG[r] * invmulG[l - 1] % MOD, (ll)(N / l) * (M / l))) %= MOD;
74
            l = r + 1;
75
        }printf("%lld\n", ans);
76
    }
77
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
78
    return 0;
79
}
80

81
template < typename T >
82
inline T read(void){
83
    T ret(0);
84
    int flag(1);
85
    char c = getchar();
86
    while(c != '-' && !isdigit(c))c = getchar();
87
    if(c == '-')flag = -1, c = getchar();
88
    while(isdigit(c)){
89
        ret *= 10;
90
        ret += int(c - '0');
91
        c = getchar();
92
    }
93
    ret *= flag;
94
    return ret;
95
}

UPD

update-2023_03_08 初稿