杂题小记（2023.03.06）

更好的阅读体验戳此进入

LG-P4548 [CTSC2006]歌唱王国

考虑发现答案为对于原串的每个 border 长度 $l$$l$（包括原串本身），$\sum _l{n}^l$$\sum_l n^l$。

原理基于 有哪些有趣的概率问题？。

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 N, M;
27
int vals[110000];
28
int nxt[110000];
29
ll powN[110000];
30
ll ans(0);
31

32
int main(){powN[0] = 1;
33
    N = read();
34
    for(int i = 1; i <= 101000; ++i)powN[i] = powN[i - 1] * N % 10000;
35
    int T = read();
36
    while(T--){
37
        M = read();
38
        ans = powN[M];
39
        for(int i = 1; i <= M; ++i)vals[i] = read();
40
        int lst(0);
41
        nxt[0] = nxt[1] = 0;
42
        for(int i = 2; i <= M; ++i){
43
            while(lst && vals[lst + 1] != vals[i])lst = nxt[lst];
44
            if(vals[lst + 1] == vals[i])++lst;
45
            nxt[i] = lst;
46
        }int cur(nxt[M]);
47
        while(cur)
48
            (ans += powN[cur]) %= 10000,
49
            cur = nxt[cur];
50
        printf("%04lld\n", ans);
51
    }
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-P4916 [MtOI2018]魔力环

纯组合意义是不可能的，这辈子都不可能的。

发现本质不同关键字，不难想到群论，对于本题可以使用 Burnside，考虑令 $g(i)$$g(i)$ 表示置换为旋转 $i$$i$ 的不动点的数量，令 $f(i)$$f(i)$ 表示存在 $i$$i$ 个环的方案数，这样答案不难想到即为：

考虑经典转化，即 $f(i)=g(gcd(n,i))$$f(i) = g(\gcd(n, i))$。

转化为：

考虑处理 $f(d)$$f(d)$，令 $\xi (n,m,k)$$\xi(n, m, k)$ 表示 $n+m$$n + m$ 个球染 $m$$m$ 个黑色限制为 $k$$k$ 的方案数，由将 $m$$m$ 个球可空地放入 $n$$n$ 个盒每个盒不能超过 $k$$k$ 的方案数得到，不难想到一个类似二项式反演的容斥：

即经典插板法。

则对于 $f(d)$$f(d)$，应有：

同时注意对于 $d\nmid m$$d \nmid m$，显然 $f(d)=0$$f(d) = 0$。

xxxxxxxxxx
97
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 (998244353ll)
24
#define LIM (210000)
25

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

29
int N, M, K;
30
ll phi[LIM + 100];
31
bitset < LIM + 100 > notPrime;
32
basic_string < int > Prime;
33
ll fact[LIM + 100], inv[LIM + 100];
34

35
int main(){
36
    auto qpow = [](ll a, ll b)->ll{
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
    auto Init = [qpow](void)->void{
45
        phi[1] = fact[0] = 1;
46
        for(int i = 2; i <= LIM; ++i){
47
            if(!notPrime[i])phi[i] = i - 1, Prime += i;
48
            for(auto p : Prime){
49
                if((ll)i * p > LIM)break;
50
                notPrime[i * p] = true;
51
                if(i % p == 0)phi[i * p] = p * phi[i] % MOD;
52
                else phi[i * p] = phi[p] * phi[i] % MOD;
53
                if(i % p == 0)break;
54
            }
55
        }
56
        for(int i = 1; i <= LIM; ++i)fact[i] = fact[i - 1] * i % MOD;
57
        inv[LIM] = qpow(fact[LIM], MOD - 2);
58
        for(int i = LIM - 1; i >= 0; --i)inv[i] = inv[i + 1] * (i + 1) % MOD;
59
    };Init();
60
    auto GetC = [](ll n, ll m)->ll{
61
        if(n < m || n < 0 || m < 0)return 0;
62
        return fact[n] * inv[m] % MOD * inv[n - m] % MOD;
63
    };
64
    auto Cal = [qpow, GetC](ll N, ll M, ll K)->ll{
65
        ll ret(0);
66
        for(int i = 0, flag = 1; i * (K + 1) <= M; ++i, flag *= -1)
67
            (ret += ((flag * GetC(N, i) * GetC(M - i * (K + 1) + N - 1, N - 1) % MOD) + MOD) % MOD) %= MOD;
68
        (ret *= (N + M) * qpow(N, MOD - 2) % MOD) %= MOD;
69
        return ret;
70
    };
71
    ll ans(0);
72
    N = read(), M = read(), K = read();
73
    if(N == M)printf("%d\n", K >= N ? 1 : 0), exit(0);
74
    for(int i = 1; i <= N; ++i)
75
        if(N % i == 0 && M % i == 0)
76
            (ans += Cal((N - M) / i, M / i, K) * phi[i] % MOD) %= MOD;
77
    (ans *= qpow(N, MOD - 2)) %= MOD;
78
    printf("%lld\n", ans);
79
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
80
    return 0;
81
}
82

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

UPD

update-2023_03_06 初稿