跳转至

ATC & CF 选做(23Jan,23Feb)

开了一个表格用来记录近期的做题情况，这段时间的中心就差不多是 ABC DEF 了，练到能赛时做出来就可以进下一阶段了。

题目翻译大部分来自洛谷。

ABC284D - Happy New Year 2023ψ(｀∇´)ψ

给定一个正整数 \(N\le 9\times 10^{18}\)，保证 \(N=p^2q\) 且 \(p,q\) 均为质数，请求出 \(p,q\)。

翻译 by @Mars_Dingdang

\(O(n^{\frac{1}{3}})\) 做法还不会，之后补。

我是 \(O(n^{\frac{1}{4}})\) 的 Pr 做法。

就把这个当成大数求最大质因子的板子就行了，粘的两年前的板子。

Code 
  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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// author : black_trees

#include <cmath>
#include <ctime>
#include <cstdio>
#include <random>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

#define li inline
#define re register
#define ll __int128

__int128 abs_128(__int128 x){
    if(x>0){
        return x;
    }
    return -x;
}

namespace Miller_Rabin{
    const int Pcnt=12;
    const ll p[Pcnt]={2,3,5,7,11,13,17,19,61,2333,4567,24251};

    li ll pow(re ll a,re ll b,re ll p){
        re ll ans=1;
        for(;b;a=a*a%p,b>>=1){
            if(b&1){
                ans=ans*a%p;
            }
        }
        return ans;
    }

    li bool check(re ll x,re ll p){
        if(x%p==0||pow(p%x,x-1,x)^1){
            return true;
        }
        re ll t,k=x-1;
        while((k^1)&1){
            t=pow(p%x,k>>=1,x);
            if(t^1&&t^x-1){
                return true;
            }
            if(!(t^x-1)){
                return false;
            }   
        }
        return false;
    }

    inline bool MR(re ll x){
        if(x<2)return false;
        for(re int i=0;i^Pcnt;++i){
            if(!(x^p[i]))return true;
            if(check(x,p[i]))return false;
        }return true;
    }
}

namespace Pollard_Rho{
    #define Rand(x) (1ll*rand()*rand()%(x)+1)

    li ll gcd(const ll a,const ll b){return b?gcd(b,a%b):a;}

    li ll mul(const re ll x,const re ll y,const re ll X){
        ll k=(1.0L*x*y)/(1.0L*X)-1,t=x*y-k*X;
        while(t<0)t+=X;return t;
    }

    li ll PR(const re ll x,const re ll y){
        re int t=0,k=1;re ll v0=Rand(x-1),v=v0,d,s=1;
        while(true){
            v=(mul(v,v,x)+y)%x,s=mul(s,abs_128(v-v0),x);
            if(!(v^v0)||!s)return x;
            if(++t==k){if((d=gcd(s,x))^1)return d;v0=v,k<<=1;}
        }
    }

    li void Resolve(re ll x,re ll&ans){
        if(!(x^1)||x<=ans)return;
        if(Miller_Rabin::MR(x)){
            if(ans<x)ans=x;
            return;
        }
        re ll y=x;
        while((y=PR(x,Rand(x)))==x);
        while(!(x%y)){
            x/=y;
        }
        Resolve(x,ans);
        Resolve(y,ans);
    }

    li long long check(ll x){
        re ll ans=0;Resolve(x,ans);
        return ans;
    }
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    srand(time(NULL));

    int T; cin >> T;
    while(T--) {
        unsigned long long x, p, q;
        cin >> x, p = Pollard_Rho::check(x);
        x /= p;
        if(x % p == 0) q = x / p;
        else q = sqrt(x), swap(p, q);
        cout << p << " " << q << endl;
    }

    return 0;
}

// ()()()(?

ABC284F - ABCBACψ(｀∇´)ψ

对于一个长度为 \(N\) 的字符串 \(S\) 和一个整数 \(i\in [0,N]\)，定义 \(f_i(S)\) 所得的字符串为以下三者顺次连接：

  • \(S\) 的前 \(i\) 个字符；
  • 将 \(S\) 翻转得到的字符串；
  • \(S\) 的后 \(N-i\) 个字符。

例如，对于 \(S=\texttt{abc}\)，\(i=2\) 有 \(f_i(S)=\texttt{abcbac}\)。

现在有一个长度为 \(2N\) 的字符串 \(T\)，你需要求出任意一对 \((S,i)\) 满足 \(f_i(S)=T\)。如果不存在，输出 \(-1\)。

翻译 by @Mars_Dingdang

注意到 \(1\le N \le 10^6\)，不难想到 \(O(N)\) 做。

然后我们要检查，做一些匹配之类的，所以估计是字符串哈希。

直接考虑枚举 \(i\)，然后字符串 hash check 一下就行了，因为要反串，所以前后缀都要做一次。

纯傻逼，卡我自然溢出，写了一个双哈希才过。

CF1783C - Yet Another Tournamentψ(｀∇´)ψ

有 \(n\) 个选手，编号为 \(1\) 至 \(n\) ，每两个选手对战时，编号大的将会胜利。

你可以准备 \(m\) 单位时间，每准备 \(a_i\) 时间就可以赢 \(i\) 号选手。

按胜利的总次数排名，求你最高多少名。

注意到一个比较关键的点是，如果能打赢的人相同的情况下，最优的决策一定是尽量打爆 rk 高的人。

所以先排序直接暴力取，然后从后面不断贪心的拿一个，退掉一个已经选了的即可。

如果用优先队列实现会比较复杂，代码里注释掉了，是还没调出来的，后来发现可以直接前缀和（

Code 
 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
94
95
96
97
// author : black_trees

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 5e5 + 10;

int n, m;
int a[si], b[si], sum[si];
// struct node {
//     int id, cnt, val;
//     bool operator < (const node &b) const {
//         if(val == b.val) return cnt > b.cnt;
//         return val < b.val;
//     }
// } a[si];
// int b[si];

// std::priority_queue<std::pair<node, int>> q;

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    int T; cin >> T;
    while(T--) {
        // cin >> n >> m, b[0] = b[n + 1] = 0;
        // while(!q.empty()) q.pop();
        // for(int i = 1; i <= n; ++i)
        //     cin >> a[i].val, a[i].id = i, a[i].cnt = i - 1, b[i] = 0;
        // sort(a + 1, a + 1 + n);
        // int cnt = 0;
        // for(int i = 1; i <= n; ++i) {
        //     if(m - a[i].val >= 0) {
        //         m -= a[i].val, cnt++; 
        //         q.push({a[i], i});
        //     }
        //     else {
        //         if(q.empty()) break;
        //         for(int j = i; j <= n; ++j) a[i].cnt ++;
        //         for(int j = i; j <= n; ++j) {
        //             auto x = q.top();
        //             cout << x.first.id << " " << x.first.cnt << " " << x.first.val << " " << x.second << endl;
        //             if(m + x.first.val - a[i].val >= 0) {
        //                 q.pop(), m += x.first.val, m -= a[i].val;
        //                 a[x.second].cnt ++, a[i].cnt --;
        //                 q.push({a[i], i});
        //             }
        //         }
        //         break;
        //     }
        // }
        // b[cnt] += 1;
        // for(int i = 1; i <= n; ++i)
        //     b[a[i].cnt] += 1;
        // for(int i = 1; i <= n; ++i) {
        //     cout << "b[" << i << "] = " << b[i] << " ";
        // }
        // cout << endl;
        // int ans = 0;
        // for(int i = n; i >= 0; --i) {
        //     if(i == cnt) { ans++; break; }
        //     ans += b[i];
        // }
        // cout << ans << endl;
        // cout << " --- - - - -- - - " << endl;
        cin >> n >> m;
        for(int i = 1; i <= n; ++i)
            cin >> a[i], b[i] = a[i];
        sort(b + 1, b + 1 + n);
        for(int i = 1; i <= n; ++i)
            sum[i] = sum[i - 1] + b[i];

        int ans = n + 1;
        for(int i = 1; i <= n; ++i) {
            if(m >= sum[i])
                ans = min(ans, n - i + 1);
            if(i < n && m >= sum[i] + max(a[i + 1] - b[i], 0))
                ans = min(ans, n - i);
        }
        cout << ans << endl;
    }

    return 0;
}

// ()()()(?

CF1783E - Game of the Yearψ(｀∇´)ψ

Monocarp 和 Polycarp 正在玩电脑游戏。游戏特点：$ n $ 个编号从 $ 1 $ 到 $ n $ 的BOSS。

他俩将用以下方式与BOSS战斗

  • Monocarp 进行 \(k\) 次尝试撒掉boss;
  • Polycarp 进行 \(k\) 次尝试撒掉boss;
  • Monocarp 进行 \(k\) 次尝试撒掉boss;
  • Polycarp 进行 \(k\) 次尝试撒掉boss;
  • ...

Monocarp 在第 \(a_i\) 次尝试中撒掉了第 \(i\) 只BOSS。Polycarp 在第 \(b_i\) 次尝试中撒掉了第 \(i\) 只BOSS。其中一个人撒掉第 \(i\) 只BOSS后，他们就会尝试撒第 \((i+1)\) 只BOSS。并且他们的尝试计数器都会清空。撒掉第 \(n\) 只BOSS后，游戏结束。

找到从 \(1\) 到 $ n $所有的 \(k\) 值， 使得 Monocarp 可以杀死所有的BOSS。

分析一下，要让 Monocarp 把每一个都优先打掉，就要保证 \(\lceil \dfrac{a_i}{k}\rceil \le \lceil\dfrac{b_i}{k}\rceil\)。

直接暴力求复杂度 \(O(n^2)\)，快上天了，肯定要考虑 \(O(1) \sim O(\log n)\) 的单次操作。

如果 \(a_i \le b_i\) 显然不管怎么样都是 Mono 先打完。

于是我们考虑 \(a_i > b_i\) 的情况。

第一种情况是 \(k \ge a_i\)，这样显然第一轮 Mono 就打完了。

第二种情况是 \(k < a_i\)，这样的话要保证 \(\lceil \dfrac{a_i}{k}\rceil \le \lceil\dfrac{b_i}{k}\rceil\)，需要满足，只考虑最后两次 attack 的时候，Mono 打出第一次，Poly 打出第一次，此时满足 \(a_i \le k\)，这样第二次 Mono 就可以优先打掉。

本质上是 \(b_i \mod k\) 要有大于零的余数，不然因为 \(a_i > b_i\)，Poly 一定会在 Mono 之前打完。

所以 \(k \not|\ b_i\) 即可，然后注意到 \([b_i, a_i)\) 这个区间里面的数，Poly 第一次就会打掉，然后 Mono 还剩一点，这些也要筛掉。

然后我随便手玩了一下注意到，如果 \(a_i = 10, b_i = 4\) 这种情况，我筛不掉 \(3\)，会寄掉。

发现其实 \([b_i, a_i)\) 这一段的所有数的因子也是要筛掉的，其实本质是和 \(b_i \mod k \not ={0}\) 一个道理，因为我上面的想法只考虑了 \(a_i, b_i\) 在相邻的两个块里面的情况（块指数轴上按 \(k\) 分块）。

这样做可以不用考虑 \([b_i, a_i)\)，因为因子包含数本身。

Code 
 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
// author : black_trees

#include <map>
#include <set>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;

int n, m;
int a[si], b[si];
bool vis[si];
std::set<int> s;

std::vector<int> fact[si];
void get_factors(int n) {
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n / i; ++j)
            fact[i * j].emplace_back(i);
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    get_factors(si - 10);
    int T; cin >> T;
    while(T--) {
        cin >> n, s.clear();
        for(int i = 1; i <= n; ++i) 
            cin >> a[i], vis[i] = true;
        for(int i = 1; i <= n; ++i) 
            cin >> b[i], s.insert(i);
        for(int i = 1; i <= n; ++i) {
            if(a[i] <= b[i]) continue;
            auto l = s.lower_bound(b[i]), r = s.lower_bound(a[i]);
            for(auto j = l; j != r; ++j)
                for(auto x : fact[*j]) vis[x] = false;
            s.erase(l, r);
        }
        int cnt = 0;
        for(int i = 1; i <= n; ++i) {
            if(vis[i]) cnt++;
        }
        cout << cnt << endl;
        for(int i = 1; i <= n; ++i) {
            if(vis[i]) cout << i << " \n"[i == n];
        }
    }

    return 0;
}

// ()()()(?

ABC284E - Count Simple Pathsψ(｀∇´)ψ

给定一张 \(N\) 个节点 \(M\) 条边的无向图，保证每个节点的度数 \(\le 10\)。

记从任意节点回到 \(1\) 号点的不同路径总数为 \(K\)，请输出 \(\min(K,10^6)\)。

翻译 by @Mars_Dingdang

感觉没什么好说的，就是简单的 dfs。

但是我居然连把 vis 放到 dfs 外面用来回溯都忘记了？

dfs 都不会写了？？？

Code 
 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
// author : black_trees

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;

int n, m;
int tot = 0, head[si];
struct Edge { int ver, Next; } e[si << 1];
inline void add(int u, int v) { e[tot] = (Edge){v, head[u]}, head[u] = tot++; }

int ans = 0;
bool vis[si];
void dfs(int u, int fa) {
    if(ans >= 1000000) cout << "1000000" << endl, exit(0);
    vis[u] = true; ans++;
    for(int i = head[u]; ~i; i = e[i].Next) {
        int v = e[i].ver;
        if(v == fa) continue;
        if(vis[v]) continue;
        dfs(v, u);
    }
    vis[u] = false;
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    memset(head, -1, sizeof head), tot = 0;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int u, v; cin >> u >> v;
        add(u, v), add(v, u);
    }
    dfs(1, 0);
    cout << ans << endl;

    return 0;
}

CF1775C - Interesting Sequenceψ(｀∇´)ψ

因为比较懒所以这几个题就是口胡题解，代码也懒得放了。

给两个数，\(n\) 和 \(x\)，问是否存在 \(m\)，使得 \(n \& n+1 \& …… \& m = x\)，如果存在求出最小的 \(m\)，否则输出 \(-1\)。

考虑二进制下贪心即可，注意处理进位和无解。

CF1775D - Friendly Spidersψ(｀∇´)ψ

火星上有一种神秘的电子蜘蛛。

为了研究这种蜘蛛，科学家找来了其中的 \(n\) 个，每个蜘蛛有不同的腿数，用数组 \(a\) 表示。科学家们发现，有的蜘蛛互相是朋友，如果第 \(i\) 个蜘蛛和第 \(j\) 个蜘蛛是朋友的话，那么要满足 \(\operatorname{gcd}(a_{i},a_{j})≠1\)，其中 \(\operatorname{gcd}(x,y)\) 函数表示求 \(x\) 和 \(y\) 的最大公约数。

科学家发现蜘蛛可以互相发送信息。如果两只蜘蛛是朋友，那么它们可以用一秒钟直接发送消息。否则，蜘蛛必须将消息传递给他的朋友，而朋友又必须将消息传递给他的朋友，依此类推，直到消息到达收件人。

假设有一只八条腿的蜘蛛向一只 \(15\) 条腿的蜘蛛传递消息，但是由于 \(\operatorname{gcd}(8,15)=1\) 所以他不能直接发送，但它可以通过六条腿的蜘蛛发送消息，因为 \(\operatorname{gcd}(8,6)=2\) 并且 \(\operatorname{gcd}(6,15)=3\) 所以消息将会在两秒钟到达。

科学家们希望找到第 \(s\) 个蜘蛛向第 \(t\) 个蜘蛛发送消息的最短时间，以及最短路线。

考虑优化建图，只需要先筛出所有质数，将其的倍数全部连边。

相当于找公共质因子时为了方便反着算这样子，然后随便跑一跑最短路就行。

CF1775E - The Human Equationψ(｀∇´)ψ

给定 \(n\) 个数 \(a_1...a_n\)，随后你可以进行若干次操作，每次操作步骤如下：

  • 选出 \(a\) 中一个子序列（可以不连续）。

  • 把子序列中的奇数项减一，偶数项加一；或者奇数项加一，偶数项减一。

求把 \(n\) 个数全部变成 \(0\) 的最少操作次数。

\(1\le n\le2\times10^5,-10^9\le a_i\le10^9\)，多组数据。

考虑贪心的取，希望每次能让负数加，正数减，且减到 0 就不动。

考虑后减完的操作次数即可，因为只能一个一个操作，所以答案是前缀和的极差。

CF1778A - Flip Flop Sumψ(｀∇´)ψ

给定一个长度为 \(n\) 的只含有 \(1\) 或 \(-1\) 的数组 \(a\)，对其进行如下的操作：

  • 选定一个 \(i\)，满足 \(1\le i<n\)，将 \(a_i\) 修改为 \(-a_i\)，将 \(a_{i+1}\) 修改为 \(-a_{i+1}\)。

求出一次操作之后 \(\sum\limits_{i=1}^n a_i\) 的最大值。

by @zfx1569_HCl_2023

策略是显然的，枚举每一个位置计算答案即可

Code 
 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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 1e5 + 10;

int a[si];

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    int T; cin >> T;
    while(T--) {
        int n; 
        cin >> n;
        int sum = 0;
        int ans = -0x3f3f3f3f;
        for(int i = 1; i <= n; ++i)
            cin >> a[i], sum += a[i];
        for(int i = 1; i < n; ++i) {
            int x = a[i], y = a[i + 1];
            int tmp = sum - x - y;
            x *= -1, y *= -1;
            tmp += x + y;
            ans = max(ans, tmp);
        }
        cout << ans << endl;

    }

    return 0;
}

// ()()()(?

CF1778B - The Forbidden Permutationψ(｀∇´)ψ

给定 \(3\) 个整数 \(n,m,d\)、一个 \(n\) 的排列 \(p\) 和一个长度为 \(m\) 的数组 \(a\)，定义 \(\mathrm{pos}(x)\) 为 \(p\) 中 \(x\) 的下标。

数组 \(a\) 是不好的，当且仅当对于所有 \(1\le i<m\)，有 \(\mathrm{pos}(a_i)<\mathrm{pos}(a_{i+1})\le\mathrm{pos}(a_i)+d\)。

每一次操作，你可以选择 \(p\) 中的两个相邻数字并把它们交换，求最小的操作次数，使得 \(a\) 变为好的。

by @zfx1569_HCl_2023

读题要仔细一点，not good 的条件是对于所有 \(i\) 都有题面中的条件成立。

所以枚举每一个位置更新答案即可。

Code 
 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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 1e5 + 10;

int n, m, d;
int a[si], p[si], pos[si];

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    int T; cin >> T;
    while(T--) {
        cin >> n >> m >> d;
        for(int i = 1; i <= n; ++i)
            cin >> p[i], pos[p[i]] = i;
        for(int i = 1; i <= m; ++i) 
            cin >> a[i];
        int ans = n, ret = 0;
        bool f = false;
        for(int i = 1; i < m; ++i) {
            if(pos[a[i]] < pos[a[i + 1]] && pos[a[i + 1]] <= pos[a[i]] + d) {
                ans = min(ans, pos[a[i + 1]] - pos[a[i]]);
                if(n - 1 > d) ret = max(ret, pos[a[i + 1]] - pos[a[i]]);
                f = true;
            }   
            else { f = false; break; }
        }
        if(!f) cout << "0" << endl;
        else cout << min(ans, (d - ret) + 1) << endl;
    }

    return 0;
}

// ()()()(?

CF1778C - Flexible Stringψ(｀∇´)ψ

对于长度为 \(n\) 的 \(a\),\(b\) 两个字符串，\(a\) 初始最多含有 \(10\) 个不同字母。你可以选择至多 \(k\) 个不同字母，将 \(a\) 中的这些字母替换为任意字母。

你需要求出经过上述操作后，\(a,b\) 相同位置且相同字母的子串尽可能多。

数据范围：\(1 \le t \le 10^4,1 \le n \le 10^5,0 \le k \le 10\)。

注意到给定的 \(a\) 的 \(|\Sigma| \le 10\)，所以可以暴力枚举每一种字符选不选的情况。

然后暴力 check 就可以了。

Code 
 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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 30;

int n, q;
string a, b;
int ctt[si], re[si];

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    int T; cin >> T;
    while(T--) {
        memset(ctt, 0, sizeof ctt);
        cin >> n >> q;
        cin >> a >> b;
        a = ' ' + a, b = ' ' + b;
        int clz = 0;
        for(int i = 1; i <= n; ++i)
            ctt[a[i] - 'a' + 1]++;
        for(int i = 1; i <= 26; ++i)
            if(ctt[i]) ++clz, re[i] = clz - 1;

        // cout << clz << endl;

        q = min(q, clz); i64 ans = -1;
        // cout << q << endl;

        std::vector<int> opt;
        for(int msk = 0; msk < (1 << clz); ++msk)
            if(__builtin_popcount(msk) == q) opt.emplace_back(msk);

        for(auto msk : opt) {
            if(__builtin_popcount(msk) == q) {
                string tmp = a;
                for(int i = 1; i <= n; ++i)
                    if(msk >> re[tmp[i] - 'a' + 1] & 1) tmp[i] = b[i];
                // cout << tmp << endl;
                i64 cnt = 0, sum = 0;
                for(int i = 1; i <= n; ++i) {
                    if(tmp[i] == b[i]) cnt++;
                    else {
                        sum += cnt * (cnt + 1) / 2;
                        cnt = 0;
                    }
                    if(i == n) 
                        sum += cnt * (cnt + 1) / 2;
                }
                ans = max(ans, sum);
            }
        }
        cout << ans << endl;
    }

    return 0;
}

// ()()()(?

CF1778D - Flexible String Revisitψ(｀∇´)ψ

给出两个长度均为 \(n(n\leq 10^6)\) 的 01 串 \(S\) 和 \(T\)

每次随机将 \(S\) 中的某一位取反

问：第一次 \(S = T\) 时操作次数的期望

一个很经典的期望 dp 套路，是一种比较好玩的处理后效性的套路。

考虑设 \(dp(i)\) 表示由 \(i\) 个位置不同变到 \(i - 1\) 的期望代价，也就是直接只算每一步，最后算答案直接 \(\sum\limits_{i = 1}^k dp(i)\) 即可。

然后对于每一个位置有两种情况，有可能直接一步到位，也有可能先变成 \(dp(i + 1)\) 再变回来。

所以 \(dp(i) = \dfrac{n - i}{n}(dp(i) + dp(i + 1) + 1) + \dfrac{i}{n}\)，这里比较反常，自己的状态里还包含自己，不过没关系。

我们直接移项：\(\dfrac{i}{n}dp(i) = 1 + \dfrac{n - i}{n}dp(i + 1) \iff dp(i) = \dfrac{n}{i} + \dfrac{n - i}{i}dp(i + 1)\)。

好，然后做完了。

这么做的原因是，因为状态可能转移过去还转移回来，但是发现转移的区间是有限的，于是我们可以拆分问题，只需要考虑每一个小部分的答案最后合并即可。

思考这种 dp 的时候不能被“一定要找到一个另外一层的状态来表示这个状态”这样的套路限制，要直接根据定义写出来，后效性可以移项处理。

这种应该在期望 dp 里面比较常见，就是因为是对序列整体随机选，所以直接线性 dp 做不了，不然状压不然就这样拆分。

Code 
  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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;
using ldb = long double;
using u64 = unsigned long long;

constexpr i64 safe_mod(i64 x, i64 m) { return x %= m, x < 0 ? x + m : x; }
constexpr i64 pow_mod_constexpr(i64 x, i64 n, int m) {
    if(m == 1) return 0;
    unsigned _m = m; uint64_t r = 1, _x = safe_mod(x, m);
    for(; n; n >>= 1, _x = _x * _x % _m) if(n & 1) r = r * _x % m;
    return r;
}
constexpr bool is_prime_constexpr(int n) {
    if(n <= 1) return false;
    if(n == 2 || n == 7 || n == 61) return true;
    if(n % 2 == 0) return false;
    i64 d = n - 1; while(~d & 1) d /= 2;
    for(i64 a : {2, 7, 61}) {
        i64 t = d, y = pow_mod_constexpr(a, t, n);
        while(t != n - 1 && y != 1 && y != n - 1) y = y * y % n, t <<= 1;
        if(y != n - 1 && t % 2 == 0) return false;
    }
    return true;
}
constexpr pair<i64, i64> inv_gcd(i64 a, i64 b) {
    a = safe_mod(a, b);
    if(a == 0) return {b, 0};
    i64 s = b, t = a, m0 = 0, m1 = 1;
    while(t) {
        i64 u = s / t; s -= t * u, m0 -= m1 * u;
        i64 tmp = s; s = t, t = tmp, tmp = m0, m0 = m1, m1 = tmp;
    }
    if(m0 < 0) m0 += b / s;
    return {s, m0};
}
struct Barrett_Reduction {
    unsigned m; uint64_t im;
    Barrett_Reduction(unsigned m) :m(m), im(~0ull / m + 1) {}
    unsigned mul(unsigned a, unsigned b) const {
        uint64_t z = (uint64_t)a * b, x = (__uint128_t)z * im >> 64; unsigned v = z - x * m;
        return m <= v ? v + m : v;
    }
};
template<int m> struct static_modint {
    using _mint = static_modint;
public:
    static _mint raw(int v) { _mint x; return x._v = v, x; }
    static_modint() :_v(0) {}
    template<class __Tp> static_modint(__Tp v) { i64 x = v % m; _v = x < 0 ? x + m : x; }
    unsigned val() const { return _v; }
    _mint& operator ++ () { if(++_v == m) _v = 0; return *this; }
    _mint& operator -- () { if(!_v--) _v = m - 1; return *this; }
    _mint operator ++ (int) { _mint res = *this; ++*this; return res; }
    _mint operator -- (int) { _mint res = *this; --*this; return res; }
    _mint& operator += (const _mint& rhs) { _v += rhs._v; if(_v >= m) _v -= m; return *this; }
    _mint& operator -= (const _mint& rhs) { _v -= rhs._v; if(_v >= m) _v += m; return *this; }
    _mint& operator *= (const _mint& rhs) { uint64_t z = _v; z *= rhs._v, _v = z % m; return *this; }
    _mint& operator /= (const _mint& rhs) { return *this = *this * rhs.inv(); }
    _mint operator + () const { return *this; }
    _mint operator - () const { return _mint() - *this; }
    _mint pow(i64 n) const { assert(0 <= n); _mint x = *this, r = 1; for(; n; n >>= 1, x *= x) if(n & 1) r *= x; return r; }
    _mint inv() const{ if(prime) { assert(_v); return pow(m - 2); } else { auto eg = inv_gcd(_v, m); assert(eg.first == 1); return eg.second; } }
    friend _mint operator + (const _mint& lhs, const _mint& rhs) { return _mint(lhs) += rhs; }
    friend _mint operator - (const _mint& lhs, const _mint& rhs) { return _mint(lhs) -= rhs; }
    friend _mint operator * (const _mint& lhs, const _mint& rhs) { return _mint(lhs) *= rhs; }
    friend _mint operator / (const _mint& lhs, const _mint& rhs) { return _mint(lhs) /= rhs; }
    friend bool operator == (const _mint& lhs, const _mint& rhs) { return lhs._v == rhs._v; }
    friend bool operator != (const _mint& lhs, const _mint& rhs) { return lhs._v != rhs._v; }
private:
    unsigned _v;
    static constexpr bool prime = is_prime_constexpr(m);
};
using modint = static_modint<998244353>;

const int si = 1e6 + 10;

modint dp[si];
int n, a[si], b[si];

void init() { }

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    int T; cin >> T;
    while(T--) {
        init();
        cin >> n;
        for(int i = 1; i <= n; ++i) {
            char ch; cin >> ch;
            if(ch == '1') a[i] = 1;
            else a[i] = 0;
        }
        int cnt = 0;
        for(int i = 1; i <= n; ++i) {
            char ch; cin >> ch;
            if(ch == '1' && a[i] != 1) ++cnt;
            if(ch == '0' && a[i] != 0) ++cnt;
        }

        modint mn = n;
        dp[n] = 1, dp[0] = 0;
        for(int i = n - 1; i >= 0; --i) {
            modint trans = n - i;
            if(i != 0)
                dp[i] = (dp[i + 1] * trans + mn) / i;
        }
        for(int i = 1; i <= n + 1; ++i) {
            dp[i] = dp[i - 1] + dp[i];
        }
        cout << dp[cnt].val() << endl;
    }

    return 0;
}

// ()()()(?

ABC288D Range Add Queryψ(｀∇´)ψ

给定一个长为 \(N\) 的序列，常数 \(k\)， \(M\) 次询问，判断 \([l, r]\) 内的子序列是否为 good 的。

一个序列被认为是 good 的，当且仅当用以下操作可以使 该序列的所有元素值都变为 \(0\)

选定两个整数 \(c\) , \(i\) ，使区间 \([i, i + k - 1]\) 内的元素同时减去 $c $

对于每次询问，输出 \(\texttt{Yes}\) 或者 \(\texttt{No}\)

\(N, Q \le 2e5\)

发现这个题是对区间进行操作。

我们尝试观察答案的形式，就是几个长度相等的区间覆盖了一下。

注意到因为区间长度相等，所以覆盖之后本质上等价于一个代价为重合的区间权值之和的区间，问题转化为一个一个一个端点不重叠区间的情况。

很容易想到考虑差分意义，这样就是让一个子串的差分数组全部变成零，每次操作可以操作两个组成了长度为 \(k + 1\) 的区间的点。

可以考虑把他们分成多个同余类，那么问题等价于可以对每个同余类内相邻的两个数操作，显然需要差分意义下每个同余类内的和为 0，不过需要特殊考虑两个端点，因为 \(r + 1\) 并不在考虑范围之内，而如果直接取原序列差分这一段，头上一个元素不是对的。

如果直接扫复杂度显然不满足，我们可以在差分之后直接把每个同余类的贡献相互加一下，最后判两个端点就行，这个顺序需要注意，如果扫描剩余系的时候是从前来的，你要倒序加贡献，不然开头位置的贡献不好处理，复杂度 \(O(Qk)\)

Code 
 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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;

int n, k, a[si], q;

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> k, a[0] = 0;
    std::vector<int> c(n + 2), d;
    for(int i = 1; i <= n; ++i) 
        cin >> a[i], c[i] = a[i] - a[i - 1];
    cin >> q, d = c;
    for(int i = n; i >= 1; --i) {
        if(i + k <= n) d[i] += d[i + k];
    }
    while(q--) {
        int l, r; cin >> l >> r;
        bool f = true;
        for(int w = l; w <= l + k - 1; ++w) {
            int mx = w + (r - w + 1) / k * k;
            if(mx != r + 1) {
                f &= (d[w] + ((w == l)? a[l - 1] : 0) == ((mx + k <= n) ? d[mx + k] : 0));
            }
        }
        if(f) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}

// ()()()(?

这题想的时候没考虑转化过后的再次转化，想到考虑差分意义就没继续转化问题了。

这题关键点之一恰好就有在差分意义上，操作长成什么样。

ABC288E Wish Listψ(｀∇´)ψ

商店里有 \(N\) 件商品，标号 \(1\sim N\)，第 \(i\) 件商品有底价 \(A_i\) 且只有一件。

Takahashi 想要买其中的 \(M\) 件商品，分别是标号 \(X_1,X_2,\ldots,X_M\) 的商品。

他会按照以下的方式买东西：

若还剩 \(r\) 件商品没有购买过，选择一个符合 \(1\le j\le r\) 的 \(j\)，付这件商品的底价加上 \(C_j\) 的钱购买其中标号第 \(j\) 小的商品。

求出买到他想要的商品所付的最小价钱。

注意他也可以买不想要的商品。

\(1\le M\le N\le 5000\)，值域 \(1e9\).

看数据范围猜测应该是一个 \(O(n^2)\) 的 dp 或者贪，可能就是要对每个位置枚举一下。

先抽象一下问题，本质上就是让你选出一个给定集合的超集，使得选出这个超集的代价最小。

有一种想法是标记有没有被选，这个是不现实的。

发现问题最困难的地方其实就在于，你对于一个物品，你不太能很好的知道它在什么时候在什么位置上，应该怎么决策。

所以我们想要钦定 \(i\) 在第几个位置选，或者是找出之前选了哪些，又或者是考虑能不能处理掉之前的影响。

可以发现，如果我们选了比 \(i\) 位置更靠后的物品，对 \(i\) 的决策是没有影响的，所以我们只需要考虑 \(i\) 前面造成的影响，于是我们记一下前面选了多少个就行，然后 dp 的阶段就出来了。

所以设 \(dp(i, j)\) 表示考虑前 \(i\) 个位置，已经选了 \(j\) 个，且 \(1 \sim i\) 中所有需要选的数都已经选上的最小代价。

转移也很方便，考虑当前位置选或者不选即可，选的话转移直接取 \(\min\limits_{k = i - j + 1}^i c_k\) 就行。

然后答案是 \(\min\limits_{i=m}^ndp(n, i)\)，初始化 \(dp(i,0)=0\)，其它 \(+\infty\) 即可。

Code 
 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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

#define int long long

const int si = 5e3 + 10;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, m, a[si], c[si];
bool b[si];
int dp[si][si], cost[si][si];

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> c[i];
    for(int i = 1, x; i <= m; ++i) cin >> x, b[x] = true;

    for(int l = 1; l <= n; ++l) {
        cost[l][l] = c[l];
        for(int r = l + 1; r <= n; ++r) {
            cost[l][r] = min(cost[l][r - 1], c[r]);
        }
    }

    memset(dp, 0x3f, sizeof dp);
    for(int i = 0; i <= n; ++i)
        dp[i][0] = 0;

    int cnt = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = cnt; j <= i; ++j) {
            if(j != cnt) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + a[i] + cost[i - j + 1][i]);
            if(b[i] == false) dp[i][j] = min(dp[i - 1][j], dp[i][j]);
        }
        if(b[i]) ++cnt;
    } 

    int ans = inf;
    for(int i = m; i <= n; ++i)
        ans = min(ans, dp[n][i]);
    cout << ans << endl;

    return 0;
}

// ()()()(?

这题考虑的时候只考虑到了怎么消除这个影响，想到了记录当前选了多少个，但是没有清晰的想到这个“没有影响”的观察，于是设计不出状态。

因为卡死之后并没有回退考虑这个状态哪里出了问题，需求是什么，怎么解决。

ABC288F Integer Divisionψ(｀∇´)ψ

给定一个 \(n\) 位数 \(X\)，把 \(X\) 分成若干段，得分为每一段的乘积（可以不分割，得分为 \(X\)）。求所有分法得分之和，模 \(998244353\)。

Translate by xionglangqi

注意到这个题是对于所有可能的分割求代价之和。

套路地，我们不考虑暴力算 \(f\)，而是考虑怎么确定贡献。

先直接观察 \(f(X)\) 在给定 \(X\) 的情况下怎么算，就直接按着这个分割一下就可以。

注意到这个东西并不存在明显的基底可以用来计算，发现做法要求 \(O(n)\)，于是我们可以考虑一位一位递推。

也就是考虑怎么从 \(1\sim n - 1\) 这个子串的状态 \(\sum f_{n - 1}(X)\) 转移到 \(\sum f_n(X)\)。

很显然就考虑第 \(i\) 位会做什么贡献，显然可以乘法分配律一下，再加上一个 \(\times 10\) 的贡献：

\(dp(i) = 10 * dp(i - 1) + a(i) \times \sum\limits_{j = 1}^{i - 1} dp(j)\)。

后面那坨前缀和记一下就行，复杂度 \(O(n)\)。

Code 
 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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

#define int long long

const int si = 2e5 + 10;
const int mod = 998244353;

int n, a[si];

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    string s;
    cin >> n, cin >> s;
    for(int i = 1; i <= n; ++i) {
        a[i] = (int)(s[i - 1] - '0');
    }

    int ans = 0, sum = 1;
    for(int i = 1; i <= n; ++i) {
        (ans *= 10ll) %= mod;
        (ans += (1ll * sum * a[i])) %= mod;
        (sum += ans % mod) %= mod;
    }
    cout << ans << endl;

    return 0;
}

// ()()()(?

这题很套路，想的时候在分配律那个地方略微卡了一下，原因可能是因为当时心情比较浮躁。

ABC289D Step Up Robotψ(｀∇´)ψ

简单垃圾题，不说了。

ABC289E Swap Placesψ(｀∇´)ψ

给定一个 \(n\) 个点 \(m\) 条边的无向图，点有点权，值可以为 \(0\) 或 \(1\)。两个人分别在点 \(1\) 和 \(n\)，每次他们同时向自己这个结点的任意一个邻居移动，任意时刻，他们所在的结点的权值不得相同。最后要使得他们互相交换位置。输出最小次数或输出无解。\(n,m\le2\times10^3\)。

也没啥好说的，其实就是因为，直接找不好做，我们对每个节点设一个状态装一下限制，另外一个限制在转移的时候表达就行。

转移可以利用 bfs 做。

Code 
 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
// author : black_trees

#include <cmath>
#include <queue>
#include <tuple>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 2e3 + 10;

int n, m;
int tot = 0, head[si];
struct Edge { int ver, Next; } e[si << 1];
inline void add(int u, int v) { e[tot] = (Edge){v, head[u]}, head[u] = tot++; }

int c[si];
int dp[si][si];

std::queue<std::tuple<int, int, int>> q;

void Init() {
    tot = 0; 
    memset(head, -1, sizeof head);
    while(q.size()) q.pop();
    memset(dp, -1, sizeof dp);
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    int T; cin >> T;
    while(T--) {
        Init();
        cin >> n >> m;
        for(int i = 1; i <= n; ++i) {
            cin >> c[i];
        }
        for(int i = 1; i <= m; ++i) {
            int u, v; 
            cin >> u >> v;
            add(u, v), add(v, u);
        }

        q.push(make_tuple(0, 1, n));
        while(!q.empty()) {
            auto [dis, u, v] = q.front();
            q.pop();
            if(dp[u][v] != -1) continue;
            dp[u][v] = dis;
            for(int i = head[u]; ~i; i = e[i].Next) {
                for(int j = head[v]; ~j; j = e[j].Next) {
                    if(c[e[i].ver] != c[e[j].ver]) q.push(make_tuple(dis + 1, e[i].ver, e[j].ver));
                }
            }
        }

        cout << dp[n][1] << endl;
    }

    return 0;
}

// ()()()(?

这题想的时候纯属智障了，简单 dp 模型不会。

ABC289F Teleporter Takahashiψ(｀∇´)ψ

在坐标系中有一个起始点 \((s_x,s_y)\) 和一个矩形 \(\{(x,y)|a-0.5\le x\le b+0.5,c-0.5\le x\le d+0.5\}\)，每次操作可以选中一个矩形内的整点并把当前点移到与该点对称的位置，问能否在 \(10^6\) 次操作以内到达目标点 \((t_x,t_y)\)

如能请输出Yes并给出任意一个方案，如不能输出No

给出的所有横纵坐标都是 \(\le 2\times10^5\) 的非负整数

可以手搓样例观察到一个小小的性质。

就是我们可以利用一段区间 \([a,b]\)，直接选 \((a, y), (a + 1, y)\) 两次，就能让它在一个方向上前进 \(2\) 个单位。

减小就反过来，然后两个维度的限制可以套路地分开来做。

简单判断一下无解就可以了，因为本题的数据范围限制，保证了这个不会超限制。

Code 
 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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

int sx, sy;
int tx, ty;
int a, b, c, d;

void Map(int x, int y) {
    sx = x * 2 - sx;
    sy = y * 2 - sy;
    cout << x << " " << y << endl;
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> sx >> sy;
    cin >> tx >> ty;
    cin >> a >> b >> c >> d;
    bool even = (a != b || sx == tx) && (c != d || sy == ty);
    bool odd = (a != b || sx + tx == a + b) && (c != d || sy + ty == c + d);
    bool nsam = ((sx & 1) != (tx & 1)) || ((sy & 1) != (ty & 1));

    if(nsam || (!even && !odd)) return cout << "No" << endl, 0;

    cout << "Yes" << endl; 

    if(!even) Map(a, c);    

    while(sx < tx) Map(a, c), Map(a + 1, c);
    while(sy < ty) Map(a, c), Map(a, c + 1);
    while(sx > tx) Map(a + 1, c), Map(a, c);
    while(sy > ty) Map(a, c + 1), Map(a, c);

    return 0;
}

这个就是构造题里一个很重要的思想，考察极端边界情况，在限制次数内一点一点凑出答案。

ABC290D Markingψ(｀∇´)ψ

有 \(n\) 个排成一个环的格子，编号为 \(0\sim n-1\)。现在进行如下操作：

  • 选择 \(0\) 号格子，将其打上标记。
  • 选择 \(d\) 个格子后的第一个尚未被标记的格子，将其打上标记。
  • 重复执行直到所有格子都被打上标记。

你需要输出第 \(k\) 次标记的格子的编号。

共 \(T\) 组数据。\(1\le T\le 10^5\)，\(1\le k\le n\le10^9\)，\(1\le d\le 10^9\)。

—— by Register_int

可以注意到一个事情是，这里就是类似哈希表的一个过程。

不难想到，我们会把原来的方块按位置分成多个同余类，且他们构成完全剩余系。

有一些同余类长度不完整，分两段算一下就行，或者可以考虑推个式子。

Code 
 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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;

void solve(int n, int d, int k) {   
    k--;
    int Gcd = n / __gcd(n, d);
    cout << d * k % n + k / Gcd << endl;
}

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    int T; cin >> T; int tt = T;
    while(T--) {
        int n, d, k;
        cin >> n >> d >> k;
        solve(n, d, k); continue;
        d %= n;
        int len = ceil(double(n) / double(d)); // 每个同余类的长度。
        int full = (double(n) / double(len));// 多少个完整的剩余系。
        int r = n - full, bel; // belongs to which.
        if(k <= full * len) {
            bel = ceil(double(k) / double(len));
            k %= len, k = (k + 1) % len;
        }
        else {
            bel = ceil(double(k - (full * len)) / double(len - 1)) + full;
            k -= full * len, k %= (len - 1), k = (k + 1) % (len - 1);
        }
        // cout << "Case" << T - tt << ":\n";
        bel--, cout << bel + (d * k) << endl;
        // cout << "bel = " << bel << " len = " << len << " full = " << full << " k = " << k << " d = " << d << endl; 
    }

    return 0;
}

// ()()()(?

考虑的时候只考虑了分段的拆分做法，没想到怎么直接找到一个式子代替问题。

ABC290E Make it Palindromeψ(｀∇´)ψ

定义一个序列 \(X\) 的贡献 \(f(X)\) 为，修改 \(X\) 中的一些位置，使得 \(X\) 变为回文的最小修改次数。

对给定的，长度为 \(N\) 的序列 \(A\)，求 \(A\) 的所有子串的贡献之和。

\(1\le N \le 2 \times 10^5, 1\le A_i \le N\)。

Translate by black_trees.

这类问题还是那么的套路。

我们考虑什么东西会做出贡献，其实就是一个点对 \((i, j),a_i \not= a_j\)。

这个东西做出的贡献，应该是钦定 \(i,j\) 相对的回文串的个数。

正着算不太好搞，于是我们反着算就行，算有多少不会做贡献。

然后随便写写就行。

Code 
 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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;

int n, a[si];
std::vector<int> pos[si];

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n; int ans = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        pos[a[i]].emplace_back(i);
    }

    int ret = 0;
    for(int i = 1; i <= n; ++i) {
        int l = 0, r = pos[i].size() - 1;
        while(l < r) {
            if(pos[i][l] < n - pos[i][r] + 1)
                ret += (r - l) * pos[i][l], ++l;
            else ret += (r - l) * (n - pos[i][r] + 1), --r;
        }
    }

    for(int i = 1; i <= n; ++i) {
        ans += (n - i + 1) * (i / 2);
    } 
    cout << ans - ret << endl;

    return 0;
}

// ()()()(?

ABC290F Maximum Diameterψ(｀∇´)ψ

对于一个长度为 \(n\) 的正整数序列 \(X=(X_1,X_2,\cdots,X_n)\)，定义 \(f(X)\) 为：

  • 对于所有节点数量为 \(n\)，且点 \(i\) 的度数恰好为 \(X_i\) 的树，其直径的最大值。如不存在，则值为 \(0\)。

你需要对于所有长度为 \(n\) 的正整数序列 \(X\) 计算 \(f(X)\) 的和，可以证明其为有限值。答案对 \(998244353\) 取模。

\(T\) 组数据。\(1\le T\le2\times10^5\)，\(2\le n\le10^6\)。

—— by Register_int

我们拿到这题，仍旧是套路的考虑算贡献。

但是注意到这个 \(f(X)\) 的定义是，对于所有 \(X\) 能构造出的树里，最大的直径，相当于有两个 max 套在一起，直接求和换方式算贡献不好处理。

所以我们考虑观察一下，对于一个给定的 \(X\)，\(f(X)\) 应该是什么样子的。

有一个结论：任意合法的 \(X\) 必然包含至少两个 \(X_i = 1\) 的元素

这个是显然的，极端情况就是一条链。

这个结论启发我们，我们可以考虑尽量长的构造出一条链。

做法很简单，选两个 \(X_i = 1\) 的点作为端点，把所有 \(X_i \not= 1\) 的节点扔到中间，其他的 \(X_i = 1\) 的节点挂在中间就行。

可以证明这个做法是正确的：

证明：

钦定恰好有 \(k\) 个 \(X_i = 1\) 的节点，那么剩下的度数是 \(2n - 2 - k\)（由树的性质，度数之和为 \(2n-2\)）。

我们考虑把这条链的度数也减去，就是这 \(n - k\) 个节点之间的 \(n - k - 1\) 条边乘二，在加上两边的 \(2\)。

那么还剩下的度数就是 \(2n - 2 - k - 2(n - k - 1) - 2 = k\)，那恰好就能构造出来。

好，现在我们考虑计数，注意到排序过后相等的 \(X\) 的 \(f(X)\) 显然相等，我们算一下方案数就行。

可以发现计数的阶段应该是 \(k\)，所以我们考虑钦定某些位置都是 \(1\)，这部分方案数是 \(\dbinom{n}{k}\)，剩下的部分就全部需要 \(1\)，且我们要让这 \(n - k\) 个 \(X_i\) 的 \(\sum = 2n - 2 - k\)。

为了方便直接给每个节点减去 \(2\)，问题转化为插板法，这部分方案数是 \(\dbinom{n - 3}{n - k - 1}\)。

直径长度为 \(n - k + 1\)，那么答案就为 \(\sum\limits_{k = 1}^n \dbinom{n}{k} \dbinom{n - 3}{n - k - 1}(n - k + 1)\)。

这个显然不行，我们推一下式子。

注意到这个东西长的很像一个恒等式：\(\sum\limits_{i = 0}^k\dbinom{n}{i}\dbinom{m}{k - i} = \dbinom{n + m}{k}\)，这东西可以直接组合意义证明，听说也叫做范德蒙德卷积。

但是有一坨 \(n - k + 1\)，不好化，又想到有一个恒等式：\(k\dbinom{n}{k} = n\dbinom{n - 1}{n - k}\)

发现 \(n - k + 1\) 那一坨可以拆开变成 \(n - k - 1\)，我们可以把 \(k\) 消掉，系数写到前面。

于是我们写出：

\[ \sum\limits_{k = 1}^n \dbinom{n}{k} \dbinom{n - 3}{n - k - 1}(n - k + 1) \iff \\ \sum\limits_{k = 1}^n \dbinom{n}{k} \dbinom{n - 3}{n - k - 1}(n - k - 1) + 2\sum\limits_{k = 1}^n\dbinom{n}{k} \dbinom{n - 3}{n - k - 1} \iff \\ (n - 3)\sum\limits_{k = 1}^n \dbinom{n}{k} \dbinom{n - 4}{n - k - 2} + 2\sum\limits_{k = 1}^n\dbinom{n}{k} \dbinom{n - 3}{n - k - 1} \]

根据范德蒙德卷积公式，可以得到：

\(ans = (n - 3)\dbinom{2n - 4}{n - 2} + 2\dbinom{2n - 3}{n - 1}\)

然后就可以线性做了。

Code 
  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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;
using ldb = long double;
using u64 = unsigned long long;

constexpr i64 safe_mod(i64 x, i64 m) { return x %= m, x < 0 ? x + m : x; }
constexpr i64 pow_mod_constexpr(i64 x, i64 n, int m) {
    if(m == 1) return 0;
    unsigned _m = m; uint64_t r = 1, _x = safe_mod(x, m);
    for(; n; n >>= 1, _x = _x * _x % _m) if(n & 1) r = r * _x % m;
    return r;
}
constexpr bool is_prime_constexpr(int n) {
    if(n <= 1) return false;
    if(n == 2 || n == 7 || n == 61) return true;
    if(n % 2 == 0) return false;
    i64 d = n - 1; while(~d & 1) d /= 2;
    for(i64 a : {2, 7, 61}) {
        i64 t = d, y = pow_mod_constexpr(a, t, n);
        while(t != n - 1 && y != 1 && y != n - 1) y = y * y % n, t <<= 1;
        if(y != n - 1 && t % 2 == 0) return false;
    }
    return true;
}
constexpr pair<i64, i64> inv_gcd(i64 a, i64 b) {
    a = safe_mod(a, b);
    if(a == 0) return {b, 0};
    i64 s = b, t = a, m0 = 0, m1 = 1;
    while(t) {
        i64 u = s / t; s -= t * u, m0 -= m1 * u;
        i64 tmp = s; s = t, t = tmp, tmp = m0, m0 = m1, m1 = tmp;
    }
    if(m0 < 0) m0 += b / s;
    return {s, m0};
}
struct Barrett_Reduction {
    unsigned m; uint64_t im;
    Barrett_Reduction(unsigned m) :m(m), im(~0ull / m + 1) {}
    unsigned mul(unsigned a, unsigned b) const {
        uint64_t z = (uint64_t)a * b, x = (__uint128_t)z * im >> 64; unsigned v = z - x * m;
        return m <= v ? v + m : v;
    }
};
template<int m> struct static_modint {
    using _mint = static_modint;
  public:
    static _mint raw(int v) { _mint x; return x._v = v, x; }
    static_modint() :_v(0) {}
    template<class __Tp> static_modint(__Tp v) { i64 x = v % m; _v = x < 0 ? x + m : x; }
    unsigned val() const { return _v; }
    _mint& operator ++ () { if(++_v == m) _v = 0; return *this; }
    _mint& operator -- () { if(!_v--) _v = m - 1; return *this; }
    _mint operator ++ (int) { _mint res = *this; ++*this; return res; }
    _mint operator -- (int) { _mint res = *this; --*this; return res; }
    _mint& operator += (const _mint& rhs) { _v += rhs._v; if(_v >= m) _v -= m; return *this; }
    _mint& operator -= (const _mint& rhs) { _v -= rhs._v; if(_v >= m) _v += m; return *this; }
    _mint& operator *= (const _mint& rhs) { uint64_t z = _v; z *= rhs._v, _v = z % m; return *this; }
    _mint& operator /= (const _mint& rhs) { return *this = *this * rhs.inv(); }
    _mint operator + () const { return *this; }
    _mint operator - () const { return _mint() - *this; }
    _mint pow(i64 n) const { assert(0 <= n); _mint x = *this, r = 1; for(; n; n >>= 1, x *= x) if(n & 1) r *= x; return r; }
    _mint inv() const{ if(prime) { assert(_v); return pow(m - 2); } else { auto eg = inv_gcd(_v, m); assert(eg.first == 1); return eg.second; } }
    friend _mint operator + (const _mint& lhs, const _mint& rhs) { return _mint(lhs) += rhs; }
    friend _mint operator - (const _mint& lhs, const _mint& rhs) { return _mint(lhs) -= rhs; }
    friend _mint operator * (const _mint& lhs, const _mint& rhs) { return _mint(lhs) *= rhs; }
    friend _mint operator / (const _mint& lhs, const _mint& rhs) { return _mint(lhs) /= rhs; }
    friend bool operator == (const _mint& lhs, const _mint& rhs) { return lhs._v == rhs._v; }
    friend bool operator != (const _mint& lhs, const _mint& rhs) { return lhs._v != rhs._v; }
  private:
    unsigned _v;
    static constexpr bool prime = is_prime_constexpr(m);
};
struct dynamic_modint {
    using _mint = dynamic_modint;
  public:
    static void set_mod(int m) { assert(1 <= m), bt = Barrett_Reduction(m); }
    static _mint raw(int v) { _mint x; return x._v = v, x; }
    dynamic_modint() :_v(0) {}
    template<class __Tp> dynamic_modint(__Tp v) { i64 x = v % (int)bt.m; _v = x < 0 ? x + bt.m : x; }
    unsigned val() const { return _v; }
    _mint& operator ++ () { if(++_v == bt.m) _v = 0; return *this; }
    _mint& operator -- () { if(!_v--) _v = bt.m - 1; return *this; }
    _mint operator ++ (int) { _mint res = *this; ++*this; return res; }
    _mint operator -- (int) { _mint res = *this; --*this; return res; }
    _mint& operator += (const _mint& rhs) { _v += rhs._v; if(_v >= bt.m) _v -= bt.m; return *this; }
    _mint& operator -= (const _mint& rhs) { _v += bt.m - rhs._v; if(_v >= bt.m) _v -= bt.m; return *this; }
    _mint& operator *= (const _mint& rhs) { _v = bt.mul(_v, rhs._v); return *this; }
    _mint& operator /= (const _mint& rhs) { return *this = *this * rhs.inv(); }
    _mint operator + () const { return *this; }
    _mint operator - () const { return _mint() - *this; }
    _mint pow(i64 n) const { assert(0 <= n); _mint x = *this, r = 1; for(; n; n >>= 1, x *= x) if(n & 1) r *= x; return r; }
    _mint inv() const { auto eg = inv_gcd(_v, bt.m); assert(eg.first == 1); return eg.second; }
    friend _mint operator + (const _mint& lhs, const _mint& rhs) { return _mint(lhs) += rhs; }
    friend _mint operator - (const _mint& lhs, const _mint& rhs) { return _mint(lhs) -= rhs; }
    friend _mint operator * (const _mint& lhs, const _mint& rhs) { return _mint(lhs) *= rhs; }
    friend _mint operator / (const _mint& lhs, const _mint& rhs) { return _mint(lhs) /= rhs; }
    friend bool operator == (const _mint& lhs, const _mint& rhs) { return lhs._v == rhs._v; }
    friend bool operator != (const _mint& lhs, const _mint& rhs) { return lhs._v != rhs._v; }
  private:
    unsigned _v;
    static Barrett_Reduction bt;
};
using modint = dynamic_modint;
using barrett = Barrett_Reduction;

barrett modint::bt = 998244353ll;

const int si = 2e6 + 10;

modint fact[si]; 

void Init() {
    fact[0] = 1;
    for(int i = 1; i < si; ++i) 
        fact[i] = fact[i - 1] * i;
}
modint C(int n, int m) {
    if(m < 0 || n < m) return 0;
    return fact[n] / (fact[n - m] * fact[m]);
}
int solve(int n) {
    return ((n - 3) * C(n * 2 - 4, n - 2) + 2 * C(2 * n - 3, n - 1)).val();
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    Init();

    int T; cin >> T;
    while(T--) {
        int n; 
        cin >> n;
        cout << solve(n) << endl;
    }

    return 0;
}

ABC291D,E,Fψ(｀∇´)ψ

这个太水了，就不写了。

ABC292D,E,Fψ(｀∇´)ψ

这个也太水了，不写了。

最后更新: May 9, 2023