Tsawke 的三月模拟赛题解

最佳贪污

原题 LG-P4005 小 Y 和地铁。

$O(n^2)$ $O(n)$ $90+\texttt{pts}$ ，参数较为优秀时可以 AC。

转置！转置！不择手段地转置！

原题 SP422 TRANSP2 - Transposing is Even More Fun。

双倍经验 SP419 TRANSP - Transposing is Fun。

$10\%$ 是给手画的。

$30\%$ 是任意搜索等。

$70\%$ 就是 SP419。

$100\%$ 就是加强版 SP422。

挺长时间以前写的题解：

一道很好的群论题，尤其是其中转化的思想还是很高妙的。

$0$ $a = 1, b = 2$ ：

(\begin{matrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0 & 4 & 1 & 5 & 2 & 6 & 3 & 7 \end{matrix})

$2^{a + b}$ $(1, 2, 4) \rightarrow (4, 1, 2)$ $3 - 1 = 2$ $x$ $2^{a + b} - x$ $x$ 。

$2^a$ $a$ $b$ $i \times 2^b + j \rightarrow j \times 2^b + i$ ，意义上就是将二进制位分割后交换，与上述操作等效。

$a + b$ $0/1$ $a$ $a$ $\gcd(a, a + b) = \gcd(a, b)$ ，看起来很正确，但是仔细想一下就会发现这个置换群不存在逆元，所以不是群，无法计算。

$\dfrac{a + b}{\gcd(a, b)}$ $\gcd(a, b)$ $\gcd(a, b)$ $2^{\gcd(a, b)}$ $\dfrac{a + b}{\gcd(a, b)}$ $n = \dfrac{a + b}{\gcd(a, b)}$ $0, 1, 2, \cdots, n - 1$ 。现在其满足性质，直接套用 Polya 定理，考虑经典套路，得到：

\frac{1}{n} \sum_{i = 1}^{n} (2^{gcd (a, b)})^{gcd (n, i)}

用经典的莫反思想推导：

\begin{aligned} \frac{1}{n} \sum_{i = 1}^{n} 2^{gcd (a, b) gcd (n, i)} \\ = & \frac{1}{n} \sum_{d ∣ n} \sum_{i = 1}^{n} 2^{gcd (a, b) d} [gcd (n, i) = d] \\ = & \frac{1}{n} \sum_{d ∣ n} \sum_{i = 1}^{\frac{n}{d}} 2^{gcd (a, b) d} [gcd (\frac{n}{d}, i) = 1] \\ = & \frac{1}{n} \sum_{d ∣ n} 2^{gcd (a, b) d} φ (\frac{n}{d}) \end{aligned}

$O(T(\sqrt{n} + \log n))$ $O(T(n^{\tfrac{3}{4}} + \sqrt{n} \log n))$ 强行处理即可。

加强版：

有点不太理解这道题的意义，完全就是更卡常一点，需要更加精细实现，本质没有任何变化。。

推导部分完全相同，最终式子：

\frac{1}{n} \sum_{d ∣ n} 2^{gcd (a, b) d} φ (\frac{n}{d})

$2^k$ $\dfrac{a + b}{\gcd(a, b)} \times \gcd(a, b) = a + b$ $2^k$ dfs $\varphi$ $O(\sqrt{n})$ $O((a + b) + T(\sqrt{n} + \log n))$ ，可以通过。

Upd：一种新的思路：

$a + b$ $0/1$ $a, 2a, 3a, \cdots, \dfrac{a + b}{\gcd(a, b)}a$ $0$ ）。发现这样设计即可满足置换群的所有要求，且符合题意。

$ka$ $\gcd(ka, a + b)$ $2^{\gcd(ka, a + b)}$ $n = \dfrac{a + b}{\gcd(a, b)}$ ，答案即为：

\frac{1}{n} \sum_{k = 1}^{n} 2^{gcd (k a, a + b)}

然后进行一些转化：

\begin{aligned} gcd (k a, a + b) & = gcd (a, b) \times gcd (k \frac{a}{gcd (a, b)}, \frac{a + b}{gcd (a, b)}) \\ = gcd (a, b) \times gcd (k, \frac{a + b}{gcd (a, b)}) \\ = gcd (a, b) \times gcd (k, n) \end{aligned}

接下来的步骤则与之前相同。

学习？不可能！

原题 LOJ #6672. 「XXOI 2019」惠和惠惠和惠惠惠。

大概是我目前做过所有题里最有意思的了。（推逝式子多有意思）

$5\%$ 是给 puts("0") 的。

$(0, 0)$ $(n, 0)$ $(1, 1), (1, 0), (1, -1)$ $k$ 次坐标轴，不能超过坐标轴到第四象限的方案数。

$dp(i, j)$ $(0, 0)$ $(i, 0)$ $j$ $g(i)$ $(0, 0)$ $(i, 0)$ 的方案数。

$dp(i, j) = \sum_{k = 0}^{i - 1} dp(k, j - 1) \times g(i - j)$ $dp(0, 1) = 1$ $dp(n, k)$ 。

$g$ Motzkin Numbers $n$ 点中画不相交弦的方案数。

$h(n)$ $g(n) = h(n - 2)$ $h(n) = h(n - 1) + \sum_{i = 0}^{n - 2}h(i) \times h(n - 2 - i)$ 。

$y = 1$ $y = 0$ $h(n - 1)$ 就是最后直接平着走的。

$O(n^2k)$ $30\%$ 。

$H(x) = xH(x) + x^2H^x(x) + 1$ $H(x)$ $H^2(x)$ $h(n + 2) x^n - h(n + 1)x^n$ $H^2(x)$ $x^2$ $H(x)$ $h(0) = h(1) = 1$ 。

$H(x)$ $H(0) = 1$ $\lim\limits_{x \to 0}x^x = 1$ （洛必达可证）或者说用两次洛必达给解出来求二阶导或许也能证？（存疑

$h$ $g$ $g$ $f$ ，简单推导后得到最终要求的式子：

[x^{n}] {(\frac{1 + x - \sqrt{1 - 2 x - 3 x^{2}}}{2})}^{k - 1}

$60\%$ 的数据直接跑多项式开根，然后跑多项式快速幂或者多项式乘法 + 快速幂即可。

再往下就有各种各样的做法了，这里简单提几个并丢一下链接。

$100\%$ 本题整式递推的简要推导 $F'' + F' + F = 0$ $0, 1, 2$ $O(n)$ 递推即可，线性求逆元后复杂度线性。

$80\%$ 的做法，考虑发现其为整式递推形式，考虑枚举递推的系数多项式的次数和递推长度，然后用人类智慧的高斯消元验证并求解，复杂度优秀但需要支持多项式。另一份题解（一个比较高明（有趣）的做法）。

$h$ $20^6$ $\log$ 做快速幂。题解（一个十分垃圾的做法）。

然后是一些可能用到的资料：

一类通过生成函数求线性递推式的方法.pdf

一类通过生成函数求线性递推式的方法

LOJ #6672. 「XXOI 2019」惠和惠惠和惠惠惠（生成函数，整式递推）


xxxxxxxxxx
144
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 line(i) (lines.at(i - 1))
24

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

28
int N;
29
int pos[50];
30
int status[50];
31
bool itsc[50][50];
32
int cur(0);
33
int ans(INT_MAX);
34
struct Line{int l, r;};
35
basic_string < Line > lines;
36

37
int main(){
38
    freopen("corruption.in", "r", stdin);
39
    freopen("corruption.out", "w", stdout);
40
    auto notIntersect = [](int a, int b)->bool{
41
        if(line(a).l > line(b).l)swap(a, b);
42
        switch(status[a]){
43
            case 1:{
44
                switch(status[b]){
45
                    case 1: return line(a).r < line(b).l || line(b).r < line(a).r;
46
                    case 2: return true;
47
                    case 3: return line(b).l > line(a).r;
48
                    case 4: return line(b).r > line(a).r;
49
                }break;
50
            }
51
            case 2:{
52
                switch(status[b]){
53
                    case 1: return true;
54
                    case 2: return line(a).r < line(b).l || line(b).r < line(a).r;
55
                    case 3: return line(b).r > line(a).r;
56
                    case 4: return line(b).l > line(a).r;
57
                }break;
58
            }
59
            case 3:{
60
                switch(status[b]){
61
                    case 1: return true;
62
                    case 2: return line(b).r < line(a).r || line(b).l > line(a).r;
63
                    case 3: return line(b).r > line(a).r;
64
                    case 4: return line(b).l > line(a).r;
65
                }break;
66
            }
67
            case 4:{
68
                switch(status[b]){
69
                    case 1: return line(b).r < line(a).r || line(b).l > line(a).r;
70
                    case 2: return true;
71
                    case 3: return line(b).l > line(a).r;
72
                    case 4: return line(b).r > line(a).r;
73
                }break;
74
            }
75
        }return false;
76
    };
77
    auto Intersect = [notIntersect](int i, int j)->bool{return !notIntersect(i, j);};//判断写反了，懒的改就写了个 notIntersect 转一下。。。。。。
78
    auto SetOrigin = [Intersect](void)->void{
79
        cur = 0;
80
        for(int i = 1; i <= N; ++i)for(int j = i + 1; j <= N; ++j)cur += (itsc[i][j] = itsc[j][i] = Intersect(i, j));//, printf("checking i = %d, j = %d, res = %d\n", i, j, itsc[i][j] ? 1 : 0);
81
        ans = min(ans, cur);
82
    };
83
    auto Anneal = [Intersect](void)->void{
84
        double T = 50.0, delta = 0.993;
85
        while(T > 1e-2){
86
            int idx = rndd(1, N);
87
            int val = rndd(1, 4);
88
            while(val == status[idx])val = rndd(1, 4);
89
            int nxt = cur;
90
            int lsts = status[idx]; status[idx] = val;
91
            for(int i = 1; i <= N; ++i)if(i != idx){
92
                if(itsc[idx][i] && !Intersect(idx, i))--nxt;
93
                else if(!itsc[idx][i] && Intersect(idx, i))++nxt;
94
            }
95
            if(nxt < cur || exp(-(double)(nxt - cur) / T) > (double)rndd(1, 114514) / 114514){
96
                cur = nxt;
97
                ans = min(ans, cur);
98
                for(int i = 1; i <= N; ++i)if(i != idx)itsc[idx][i] = itsc[i][idx] = Intersect(idx, i);
99
            }else status[idx] = lsts;
100
            T *= delta;
101
        }
102
    };
103
    int T = read();
104
    while(T--){
105
        memset(pos, 0, sizeof pos);
106
        memset(status, 0, sizeof status);
107
        lines.clear();
108
        ans = INT_MAX;
109
        N = read();
110
        for(int i = 1; i <= N; ++i){
111
            int val = read();
112
            if(pos[val])lines += Line{min(pos[val], i), max(pos[val], i)};
113
            else pos[val] = i;
114
        }N = lines.size();
115
        if(!N){printf("0\n"); continue;}
116
        int t = 30;
117
        while(t--){
118
            memset(itsc, 0, sizeof itsc);
119
            for(int i = 1; i <= N; ++i)status[i] = rndd(1, 4);
120
            // for(int i = 1; i <= N; ++i)printf("%d ", status[i]);
121
            // printf("\n");
122
            SetOrigin();
123
            Anneal();
124
        }printf("%d\n", ans);
125
    }
126
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
127
    return 0;
128
}
129

130
template < typename T >
131
inline T read(void){
132
    T ret(0);
133
    int flag(1);
134
    char c = getchar();
135
    while(c != '-' && !isdigit(c))c = getchar();
136
    if(c == '-')flag = -1, c = getchar();
137
    while(isdigit(c)){
138
        ret *= 10;
139
        ret += int(c - '0');
140
        c = getchar();
141
    }
142
    ret *= flag;
143
    return ret;
144
}


xxxxxxxxxx
104
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 (1000003ll)
24
#define LIMIT (1100000)
25

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

29
int A, B;
30
int N, gcdv;
31
ll ans(0);
32
ll pow2[LIMIT + 100];
33
basic_string < int > Prime;
34
bitset < LIMIT + 100 > notPrime;
35
struct Num{int v; int cnt;};
36
basic_string < Num > fact;
37

38
ll qpow(ll a, ll b){
39
    ll ret(1), mul(a);
40
    while(b){
41
        if(b & 1)ret = ret * mul % MOD;
42
        b >>= 1;
43
        mul = mul * mul % MOD;
44
    }return ret;
45
}
46
void Init(int x){
47
    fact.clear();
48
    for(auto p : Prime){
49
        if(p * p > x)break;
50
        if(x % p == 0)fact += {p, 0};
51
        while(x % p == 0)fact.back().cnt++, x /= p;
52
    }if(x != 1)fact += {x, 1};
53
}
54
void dfs(int dep = 0, ll d = 1, ll base = 1, ll div = 1){
55
    if(dep == (int)fact.size())
56
        return (ans += pow2[gcdv * (N / d)] * (d / div * base) % MOD) %= MOD, void();
57
    dfs(dep + 1, d, base, div);
58
    base *= (fact.at(dep).v - 1), div *= fact.at(dep).v;
59
    for(int i = 1; i <= fact.at(dep).cnt; ++i)
60
        d *= fact.at(dep).v, dfs(dep + 1, d, base, div);
61
}
62

63
int main(){
64
    freopen("transposition.in", "r", stdin);
65
    freopen("transposition.out", "w", stdout);
66
    for(int i = 2; i <= LIMIT; ++i){
67
        if(!notPrime[i])Prime += i;
68
        for(auto p : Prime){
69
            if(p * i > LIMIT)break;
70
            notPrime[p * i] = true;
71
            if(i % p == 0)break;
72
        }
73
    }
74
    pow2[0] = 1;
75
    for(int i = 1; i <= LIMIT; ++i)pow2[i] = pow2[i - 1] * 2 % MOD;
76
    int T = read();
77
    while(T--){
78
        A = read(), B = read();
79
        N = (A + B) / __gcd(A, B), gcdv = __gcd(A, B);
80
        Init(N);
81
        ans = 0;
82
        dfs();
83
        (ans *= qpow(N, MOD - 2)) %= MOD;
84
        printf("%lld\n", (pow2[A + B] - ans + MOD) % MOD);
85
    }
86
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
87
    return 0;
88
}
89

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


xxxxxxxxxx
66
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, K;
27
ll MOD;
28
ll dp[11000000];
29
ll inv[11000000];
30

31
int main(){
32
    freopen("slack_off.in", "r", stdin);
33
    freopen("slack_off.out", "w", stdout);
34
    N = read(), K = read(), MOD = read();
35
    if(K > N)printf("0\n"), exit(0);
36
    inv[1] = 1;
37
    for(int i = 2; i <= N + 100; ++i)inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
38
    dp[0] = 1;
39
    dp[1] = K - 1;
40
    dp[2] = (ll)K * (K - 1) / 2 % MOD;
41
    for(int i = 0; i + 3 <= N - K + 1; ++i)
42
        dp[i + 3] = (
43
            dp[i] * 3 * i % MOD * (i + 1) % MOD +
44
            dp[i + 1] * ((5 * i + 3 * K + 6) % MOD) % MOD * (i + 1) % MOD +
45
            dp[i + 2] * (i + K + 1) % MOD * (i + K + 2) % MOD
46
        ) % MOD * inv[i + 3] % MOD * inv[i + K + 2] % MOD;
47
    printf("%lld\n", dp[N - K + 1]);
48
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
49
    return 0;
50
}
51

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

Tsawke 的三月模拟赛 题解

最佳贪污

转置！转置！不择手段地转置！

学习？不可能！

Tsawke 的三月模拟赛题解