2023.02.13 模拟赛小结

更好的阅读体验戳此进入

赛时思路

T1

CF840C On the Bench。

给定序列，求序列有多少个排列满足任意相邻两数之积非完全平方数。

赛时最终想到的是质因数分解后，两数合成之后若所有质因数幂次均为偶数则为完全平方数，依此可以 $O(n^2{\log }^{2}a)$$O(n^2 \log^2 a)$ 处理每个数可以（或不可以）和哪些数相邻，这样的话如果求的不是排列而是任意序列那就是一个非常朴素的 DP 了，不过排列就完全没有想到什么复杂度正确的好做法，唯一想到了一个 $O(n^5)$$O(n^5)$ 的不知道正确性的区间 DP 做法，即考虑 $dp(l,r,x,y)$$dp(l, r, x, y)$ 表示 $[l,r]$$[l, r]$ 生成的左端点为 $x$$x$ 右端点为 $y$$y$ 的排列，然后枚举分割点转移，当然这个东西既不知道正确性又没有部分分，所以直接考虑 next_permutation()。期望 $10\mathrm{pts}$$10\mathrm{pts}$。

Code

xxxxxxxxxx
89
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
#define LIM (110000)
25

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

29
int N;
30
int A[310];
31
struct Fact{int val, cnt;};
32
basic_string < Fact > facts[310];
33
basic_string < int > legal[310];
34
bitset < LIM + 100 > notPrime;
35
basic_string < int > Prime;
36

37

38
int main(){
39
    freopen("square.in", "r", stdin);
40
    freopen("square.out", "w", stdout);
41
    N = read();
42
    // for(int i = 2; i <= LIM; ++i){
43
    //     if(!notPrime[i])Prime += i;
44
    //     for(auto p : Prime){
45
    //         if((ll)i * p > LIM)break;
46
    //         notPrime[i * p] = true;
47
    //         if(i % p == 0)break;
48
    //     }
49
    // }
50
    for(int i = 1; i <= N; ++i){
51
        int val = A[i] = read();
52
        // for(auto p : Prime){
53
        //     if((ll)p * p > val)break;
54
        //     if(val % p == 0)facts[i] += Fact{p, 0};
55
        //     while(val % p == 0)facts[i].back().cnt++, val /= p;
56
        // }if(val != 1)facts[i] += Fact{val, 1};
57
    }
58
    int ans(0);
59
    int base(1);
60
    for(int i = 1; i <= N; ++i)base *= i;
61
    for(int i = 1; i <= base; ++i){
62
        bool flag(true);
63
        for(int j = 1; j < N; ++j){
64
            ll val = (ll)A[j] * A[j + 1];
65
            if((ll)sqrt(val) * (ll)sqrt(val) == val){flag = false; break;}
66
        }if(flag)++ans;
67
        next_permutation(A + 1, A + N + 1);
68
    }printf("%d\n", ans);
69

70

71
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
72
    return 0;
73
}
74

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

T2

CF819D Mister B and Astronomers。

存在一个星星每 $T$$T$ 秒闪烁一次，存在 $n$$n$ 个科学家围成一圈循环观测星星，第一个在 $0$$0$ 秒观测，第二个在 $a_2$$a_2$ 秒观测，第三个在 $a_2+a_3$$a_2 + a_3$ 秒观测，$\cdots$$\cdots$ 第一个科学家在 $a_1+a_2+a_3+\cdots +a_n$$a_1 + a_2 + a_3 + \cdots + a_n$ 观测，$\cdots$$\cdots$。对于 $t\in [0,T)$$t \in [0, T)$，若星星第一次闪烁在 $t$$t$ 秒，那么第一次观测到这个星星的科学家将会获得 $1$$1$ 的贡献，求每个科学家的贡献。

一道十分高妙的 $\mathrm{exgcd}$$\operatorname{exgcd}$ 题，赛时大概是发现了会根据同余成环，环数是 $gcd(\sum a,T)$$\gcd(\sum a, T)$，这样的话部分分就是暴力枚举每个 $t$$t$ 然后一直枚举是否出现与对应科学家同余并计算贡献即可，不难想到若两者互质那么一定有解，而在暴力分中两者不互质的部分可能存在不再同一环内导致无解，这里一个简单的办法就是均分时间然后卡时即可，期望得分 $20\mathrm{pts}$$20\mathrm{pts}$。

Code

xxxxxxxxxx
69
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

24

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

28
int N, T;
29
int A[210000];
30
ll sumA(0);
31
int ans[210000];
32
unordered_map < ll, int > equiv;
33

34
int main(){
35
    freopen("moon.in", "r", stdin);
36
    freopen("moon.out", "w", stdout);
37
    T = read(), N = read();
38
    for(int i = 1; i <= N; ++i)sumA += (A[i] = read());
39
    equiv[0] = 1;
40
    int curs(0);
41
    for(int i = 2; i <= N; ++i)curs += A[i], equiv[curs] = i;
42
    double clock_lim = 2.0 / (double)T;
43
    for(int t = 0; t <= T - 1; ++t){
44
        double sc = (double)clock() / CLOCKS_PER_SEC;
45
        int cur(t % sumA);
46
        while(equiv.find(cur) == equiv.end() && (double)clock() / CLOCKS_PER_SEC - sc <= clock_lim)(cur += T) %= sumA;
47
        if(equiv.find(cur) != equiv.end())ans[equiv[cur]]++;
48
    }
49
    for(int i = 1; i <= N; ++i)printf("%d%c", ans[i], i == N ? '\n' : ' ');
50

51
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
52
    return 0;
53
}
54

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

T3

没找到原题。

CF793F Julia the snail。

大概就是存在一个一维空间，最小位置在 $1$$1$，最大位置为 $n$$n$，你可以随时减少位置，但只能使用 $m$$m$ 个单向传送门从 $l_i$$l_i$ 到 $r_i$$r_i$，$q$$q$ 次询问给定限定 $[x_i,y_i]$$[x_i, y_i]$ 表示你初始在 $x_i$$x_i$，并位置最小不能小于 $x_i$$x_i$，最大不能大于 $y_i$$y_i$，求最大能到达哪个位置。

部分分给的还行，前 $20\mathrm{pts}$$20\mathrm{pts}$ 白送的，后面两个部分分是传送门无重叠和询问无重叠，怎么说呢，想到的几个思路最后都被我卡掉了，理论上满的时候都是 $m^2$$m^2$ 的，不过数据比较弱又多过了 $20\mathrm{pts}$$20\mathrm{pts}$。

Code

xxxxxxxxxx
115
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

24

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

28
int N, M, Q;
29

30
// class SegTree{
31
// private:
32
//     int cnt[110000 << 2];
33
//     int sum[110000 << 2];
34
//     int lz[110000 << 2];
35
//     #define LS (p << 1)
36
//     #define RS (LS | 1)
37
//     #define MID ((gl + gr) >> 1)
38
// public:
39
//     void Pushup(int p){
40
//         sum[p] = sum[LS] + sum[RS];
41
//         cnt[p] = cnt[LS] + cnt[RS];
42
//     }
43
//     void Pushdown(int p){
44
//         if(!lz[p])return;
45

46
//     }
47
// }
48

49
struct Sline{
50
    int l, r;
51
    friend const bool operator < (const Sline &a, const Sline &b){
52
        return a.l == b.l ? a.r < b.r : a.l < b.l;
53
    }
54
}s[110000];
55

56
int main(){
57
    freopen("snail.in", "r", stdin);
58
    freopen("snail.out", "w", stdout);
59
    N = read(), M = read();
60
    for(int i = 1; i <= M; ++i)s[i].l = read(), s[i].r = read();
61
    sort(s + 1, s + M + 1);
62
    Q = read();
63
    if((ll)M * Q <= (ll)(1e8)){
64
        while(Q--){
65
            int l = read(), r = read();
66
            int curl = l, curr = l;
67
            for(int i = 1; i <= M; ++i)
68
                if(curl <= s[i].l && s[i].l <= curr && s[i].r <= r)curr = max(curr, s[i].r);
69
            printf("%d\n", curr);
70
        }
71
    }else{
72
        bool spLine(true);
73
        for(int i = 1; i <= M - 1; ++i)
74
            if(s[i].l < s[i + 1].l && s[i + 1].l < s[i].r){spLine = false; break;}
75
        if(spLine){
76
            basic_string < int > ans[110000];
77
            for(int i = M; i >= 1; --i){
78
                ans[s[i].l] += s[i].r;
79
            }
80
            for(int i = N; i >= 1; --i){
81
                basic_string < int > tmp = ans[i];
82
                for(auto v : tmp)ans[i] += ans[v];
83
            }
84
            while(Q--){
85
                int l = read(), r = read();
86
                int anss(l);
87
                for(auto v : ans[l])if(v <= r)anss = max(anss, v);
88
                printf("%d\n", anss);
89
                // for(int i = 1; i <= M; ++i)
90
                //     if(curl <= s[i].l && s[i].l <= curr && s[i].r <= r)curr = max(curr, s[i].r);
91
                // printf("%d\n", curr);
92
            }
93
        }
94
    }
95
    
96

97
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
98
    return 0;
99
}
100

101
template < typename T >
102
inline T read(void){
103
    T ret(0);
104
    int flag(1);
105
    char c = getchar();
106
    while(c != '-' && !isdigit(c))c = getchar();
107
    if(c == '-')flag = -1, c = getchar();
108
    while(isdigit(c)){
109
        ret *= 10;
110
        ret += int(c - '0');
111
        c = getchar();
112
    }
113
    ret *= flag;
114
    return ret;
115
}

正解

T1

首先有一个更高妙的转换，可以认为 $50\mathrm{\%}$$50\%$ 的部分分是一个提示，即所有数都是质数的时候问题转化为不能有相同的数相邻，而正解可以先考虑将每个数的平方质因子全部去除，这样问题即可转化为要求相邻两数不同，考虑如何处理。

存在朴素 DP，考虑按序添加数（这个东西怎么处理赛时属实是想了好久假了好久），不难发现添加 $a_{i+1}$$a_{i + 1}$ 到 $[1,i]$$[1, i]$ 的排列时，有四种情况，即两侧均为 $a_{i+1}$$a_{i + 1}$，一侧为 $a_{i+1}$$a_{i + 1}$，两侧相同且均不为 $a_{i+1}$$a_{i + 1}$，两侧不同且均不为 $a_{i+1}$$a_{i + 1}$。

显然处理排列时原序列不同顺序本质相同，于是考虑将原序列排序，依次处理 $s_i$$s_i$ 表示前 $i$$i$ 个数里有多少个 $a_{i+1}$$a_{i + 1}$。

同时令 $dp(i,j,k)$$dp(i, j, k)$ 表示考虑前 $i$$i$ 个数，有 $j$$j$ 个两侧数相同且不为 $a_{i+1}$$a_{i + 1}$，有 $k$$k$ 个两侧数均为 $a_{i+1}$$a_{i + 1}$，显然对于前两种情况，考虑应有 $2\times s_i$$2 \times s_i$ 个位置，每存在一个相邻两侧均为 $a_{i+1}$$a_{i + 1}$ 的就会减少 $1$$1$，即转移为：

对于第三种情况，同理：

对于第四种情况，同理：

同时这里我们注意一个问题，当 $a_i\ne a_{i+1}$$a_i \neq a_{i + 1}$ 时，我们原来记录的 $k$$k$ 的意义会改变，换句话说原来的 $k$$k$ 会在新的这一次变为 $j$$j$，于是此时将所有 $dp(i,j,k)$$dp(i, j, k)$ 的贡献转移到 $dp(i,j+k,0)$$dp(i, j + k, 0)$ 即可。

最终答案显然为 $dp(n,0,0)$$dp(n, 0, 0)$，复杂度 $O(n^3)$$O(n^3)$。

双倍经验 LG-P4448 [AHOI2018初中组]球球的排列。

Code

xxxxxxxxxx
91
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 N;
30
ll A[310];
31
ll s[310];
32
ll dp[2][310][310];
33
bitset < LIM + 100 > notPrime;
34
basic_string < int > Prime;
35

36
int main(){
37
    for(int i = 2; i <= LIM; ++i){
38
        if(!notPrime[i])Prime += i;
39
        for(auto p : Prime){
40
            if((ll)i * p > LIM)break;
41
            notPrime[i * p] = true;
42
            if(i % p == 0)break;
43
        }
44
    }
45
    N = read();
46
    for(int i = 1; i <= N; ++i){
47
        A[i] = read();
48
        for(auto p : Prime){
49
            if((ll)p * p > A[i])break;
50
            while(A[i] % (ll)(p * p) == 0)A[i] /= (ll)p * p;
51
        }
52
    }
53
    sort(A + 1, A + N + 1);
54
    int cnt(0);
55
    for(int i = 1; i < N; ++i)
56
        if(A[i] != A[i + 1])s[i] = 0, cnt = 0;
57
        else s[i] = ++cnt;
58
    dp[0][0][0] = 1; bool cur(0);
59
    for(int i = 0; i < N; ++i){
60
        memset(dp[cur ^ 1], 0, sizeof dp[cur ^ 1]);
61
        if(A[i] != A[i + 1])
62
            for(int j = 0; j <= N; ++j)
63
                for(int k = 1; k <= N; ++k)
64
                    if(j + k <= N)(dp[cur][j + k][0] += dp[cur][j][k]) %= MOD, dp[cur][j][k] = 0;
65
        for(int j = 0; j <= N; ++j)
66
            for(int k = 0; k <= N; ++k){
67
                if(2 * s[i] - k > 0)(dp[cur ^ 1][j][k + 1] += dp[cur][j][k] * (2 * s[i] - k) % MOD) %= MOD;
68
                if(j - 1 >= 0)(dp[cur ^ 1][j - 1][k] += dp[cur][j][k] * j % MOD) %= MOD;
69
                if(i + 1 - (2 * s[i] - k) - j >= 0)(dp[cur ^ 1][j][k] += dp[cur][j][k] * (i + 1 - (2 * s[i] - k) - j) % MOD) %= MOD;
70
            }
71
        cur ^= 1;
72
    }printf("%lld\n", dp[cur][0][0]);
73
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
74
    return 0;
75
}
76

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

T2

首先不难想到，令 $S=\sum a_i$$S = \sum a_i$，第 $i$$i$ 个科学家观测时间为 $\sum _{j=2}^i{a}_j+kS,k\in \mathbb{N}$$\sum_{j = 2}^i a_j + kS, k \in \mathbb{N}$，令 $t_i=\sum _{j=2}^i{a}_j$$t_i = \sum_{j = 2}^i a_j$，同时对于 $T$$T$，假设本次初始时间为 $\xi$$\xi$，那么可以认为需要找到第一个满足 $t_i+kS\equiv \xi (\mathrm{mod}T)$$t_i + kS \equiv \xi \pmod{T}$。

对于后者式子不难发现其为经典的群论套路，即我们发现对于某个科学家的初始点 $t_i$$t_i$，可以认为每次模意义下步进 $S$$S$，此时会构成 $gcd(S,T)$$\gcd(S, T)$ 个环，环长均为 ${\displaystyle \frac{T}{gcd(S,T)}}$$\dfrac{T}{\gcd(S, T)}$，或者说每连续 $gcd(S,T)$$\gcd(S, T)$ 个数均属于不同的环。关于这个性质似乎特别显然，不过这里我们也简单证明一下：

显然我们要证明的即为如下式子：

证明均显然。

此时我们考虑，对于一个环内的所有科学家，$\xi$$\xi$ 为环上某一点的贡献，我们要找到的就是第一个，或者说其减少最少个 $S$$S$ 遇到的 $t_i$$t_i$，这个东西不难想到，对于两个同环科学家 $t_i,t_j$$t_i, t_j$，且 $t_j$$t_j$ 在 $t_i$$t_i$ 之后，两者之间模意义下距离了多少个 $S$$S$ 就代表 $i$$i$ 的答案由多少。而对于不同环中显然互相无交无关联。

所以我们可以考虑对于一个环内的所有科学家 $t_1,t_2,\cdots$$t_1, t_2, \cdots$，我们如果能够按照其在环内的遍历顺序排序，或者说满足 $t_i$$t_i$ 之后的 $t_j$$t_j$ 一定是 $t_i$$t_i$ 经过最小次模意义下加 $S$$S$ 的操作得到的（这里如何做我们后文再叙），然后遍历一遍，此时对于相邻的 $t_i<t_j$$t_i \lt t_j$（注意此时的 $<$$\lt$ 意义是我们重载过的小于号，且两者相邻或 $i$$i$ 为末尾 $j$$j$ 为初始）存在：

转化后得到：

并且显然满足 $gcd(S,T)\mid t_j-t_i$$\gcd(S, T) \mid t_j - t_i$，满足 exgcd 的限制，注意此时 $y$$y$ 是任意的，所以仅需求出 $x$$x$ 的最小非负整数解，其即代表了 $t_i$$t_i$ 对应科学家的总贡献，也就是答案。同时注意若环内仅有一个科学家则其贡献直接为 ${\displaystyle \frac{T}{gcd(S,T)}}$$\dfrac{T}{\gcd(S, T)}$。

现在我们在将目光移回上文所述的排序过程，考虑发现该限制对应到上述方程的意义就是 $x$$x$ 最小的解，如果满足 $S\perp T$$S \perp T$ 那么我们是可以通过乘逆元转换为 $t_i\times S^{-1}modT$$t_i \times S^{-1} \bmod{T}$ 的偏序关系，但本题显然不满足，于是不难想到若其初始时位置为 $p_i=t_{i}modgcd(S,T)$$p_i = t_i \bmod{\gcd(S, T)}$，那么一定存在 $p_i+kS\equiv t_i(\mathrm{mod}T)$$p_i + kS \equiv t_i \pmod{T}$，发现此方程亦为 exgcd 形式，转换为 $Sx+Ty=t_i-p_i$$Sx + Ty = t_i - p_i$，求出 $x$$x$ 的最小非负整数解即可得到其在环中对应的位置，以其为关键字进行排序则一定满足我们上述的偏序关系。而解相同的，即同环模意义下同位置的，不难想到我们优先保留 $t_i$$t_i$ 较小的即可，较后的一定为 $0$$0$。

最终复杂度卡在排序和两次 exgcd 上，为 $O(n\log n)$$O(n \log n)$。

Tips：还有些小细节，观察所有式子发现，对于所有 $S$$S$ 和 $t_i$$t_i$ 都可以并需要进行 $S\leftarrow SmodT,t_i\leftarrow t_{i}modT$$S \leftarrow S \bmod{T}, t_i \leftarrow t_i \bmod{T}$，这是对答案无影响的。对于在 set 中排除同环模意义下同位置的，可以考虑利用 C++ 特性，重载小于号，使得只保留相同第一关键字中最先加入的，可以证明最先加入的一定最小。

附：好久没写 exgcd 了，简单重推一下吧：

要求 $ax+by=gcd(a,b)$$ax + by = \gcd(a, b)$。

显然存在 $b{x}^{\prime }+(amodb)y^{\prime }=gcd(b,amodb)$$bx' + (a \bmod{b})y' = \gcd(b, a \bmod{b})$。

又 $gcd(a,b)=gcd(b,amodb)$$\gcd(a, b) = \gcd(b, a \bmod{b})$。

整理并展开 $amodb$$a \bmod b$ 得到 $ax+by=b{x}^{\prime }+(a-\lfloor {\displaystyle \frac{a}{b}}\rfloor \times b)y^{\prime }$$ax + by = bx' + (a - \lfloor \dfrac{a}{b} \rfloor \times b)y'$。

则显然有 $x=y^{\prime },y=x^{\prime }-\lfloor {\displaystyle \frac{a}{b}}\rfloor \times y$$x = y', y = x' - \lfloor \dfrac{a}{b} \rfloor \times y$。

问题规模缩减，不断递归，直到最终 $gcd=0$$\gcd = 0$ 则回溯 $x=1,y=0$$x = 1, y = 0$ 即可。

此时得到任意解，令 $d={\displaystyle \frac{t_j-t_i}{gcd(S,T)}}$$d = \dfrac{t_j - t_i}{\gcd(S, T)}$，显然整除，则 $x\leftarrow x\times d,y\leftarrow y\times d$$x \leftarrow x \times d, y \leftarrow y \times d$ 即可，同时注意我们想要求得 $x$$x$ 得最小非负解，发现方程通解为 $x+k{\displaystyle \frac{T}{gcd(S,T)}},y-k{\displaystyle \frac{S}{gcd(S,T)}}$$x + k\dfrac{T}{\gcd(S, T)}, y - k\dfrac{S}{\gcd(S, T)}$，以 ${\displaystyle \frac{T}{gcd(S,T)}}$$\dfrac{T}{\gcd(S, T)}$ 为模数对 $x$$x$ 取模转正后求出对应的 $y$$y$ 即可找到 $x$$x$ 的最小非负解。

Code

xxxxxxxxxx
90
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;
27
ll S, T;
28
int A[210000];
29
int ans[210000];
30
int gcdv(-1);
31
struct Node{
32
    ll v; ll origin; int idx;
33
    friend const bool operator < (const Node &a, const Node &b){
34
        return a.v < b.v;
35
    }
36
};
37
unordered_map < int, set < Node > > loops;
38

39
void exgcd(ll a, ll b, ll &x, ll &y){
40
    if(!b)return x = 1, y = 0, void();
41
    exgcd(b, a % b, x, y);
42
    int tmp(x);
43
    x = y, y = tmp - a / b * y;
44
}
45
ll CalMnX(ll ti, ll tj){
46
    ll x, y; ll d = (tj - ti) / gcdv;
47
    exgcd(S, T, x, y);
48
    x *= d, y *= d;
49
    ll P = T / gcdv;
50
    x = (x % P + P) % P;
51
    y = (tj - ti - S * x) / T;
52
    return x;
53
}
54

55
int main(){
56
    T = read(), N = read();
57
    for(int i = 1; i <= N; ++i)(S += (A[i] = read())) %= T;
58
    gcdv = __gcd(S, T);
59
    loops[0].insert({Node{0, 0, 1}});
60
    ll cur(0);
61
    for(int i = 2; i <= N; ++i)
62
        (cur += A[i]) %= T,
63
        loops[cur % gcdv].insert(Node{CalMnX(cur % gcdv, cur), cur, i});
64
    for(auto loop : loops){
65
        if((int)loop.second.size() == 1){ans[loop.second.begin()->idx] = T / gcdv; continue;}
66
        for(auto it = loop.second.begin(); it != loop.second.end(); advance(it, 1)){
67
            auto nxit = it == prev(loop.second.end()) ? loop.second.begin() : next(it);
68
            ans[it->idx] = CalMnX(it->origin, nxit->origin);
69
        }
70
    }
71
    for(int i = 1; i <= N; ++i)printf("%d%c", ans[i], i == N ? '\n' : ' ');
72
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
73
    return 0;
74
}
75

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

T3

首先记录一下 @sssmzy 的部分分做法：

对于传送门无重叠，加个倍增即可保证复杂度。

对于询问无重叠，考虑暴力建图即可均摊正确复杂度。

正解分块或吉司机线段树。

//TODO （先去学吉司机线段树了。。

UPD

update-2023_02_13 初稿