2025牛客暑期多校训练营6-做题&补题记录

发挥最差的一集。做完签三个人一起卡住。算了会好起来的。

---

C Stack

推式子，维护sigma f，sigma f^2，sigma f^3，复杂度O(n)

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 5e5 + 10;
constexpr int MOD = 998244353;

int fac[N];

void init() {
    fac[0] = 1;
    for (int i = 1; i < N; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }
}

void solve() {
    int n = 5e5 + 10;
    vector<i64> s(n), s2(n), s3(n);
    s[1] = 1, s[2] = 3;
    s2[1] = 1;
    s3[1] = 1;
    for (int i = 1; i < n; ++i) {
        s[i + 1] = i * s[i] + s[i] + fac[i];
        s[i + 1] %= MOD;
        s2[i + 1] = i * s2[i] + s2[i] + 2 * s[i] + fac[i];
        s2[i + 1] %= MOD;
        s3[i + 1] = i * s3[i] + s3[i] + 3 * s2[i] + 3 * s[i] + fac[i];
        s3[i + 1] %= MOD;
    }
    // for (int i = 1; i <= 10; ++i) cout << s3[i] << " \n"[i == 10];
    int t;
    cin >> t;
    while (t--) {
        int x;
        cin >> x;
        cout << (s3[x] + MOD) % MOD << "\n";
    }
}

// i64 test(int n) {
//     // int n = 4;
//     vector<int> p(n);
//     iota(all(p), 1);
//     auto f = [&](auto p) {
//         vector<int> stk;
//         for (int x : p) {
//             //debug(x);
//             while (stk.size() && stk.back() > x) stk.pop_back();
//             stk.push_back(x);
//         }
//         // for (auto x : stk) cout << x << " \n"[x == stk.back()];
//         return stk.size();
//     };
//     i64 ans = 0;
//     do {
//         auto res = f(p);
//         //debug(res);
//         ans += res * res * res;
//     } while (next_permutation(all(p)));
//     return ans;
// }

signed main() {
    
    FIO;
    init();
    // for (int i = 1; i <= 10; ++i) cout << test(i) << " ";
        // cout << endl;
    TEST {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

L Minimum Parenthesis String

左端点降序排序区间，区间不存在左括号就在左端点放左括号，同时判是否合法。都合法，贪心的从最左边开始优先放左括号。

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using i128 = __int128;

template<typename T1,typename T2>
ostream& operator<<(ostream& o,const tuple<T1,T2>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<")";
}

template<typename T1,typename T2,typename T3>
ostream& operator<<(ostream& o,const tuple<T1,T2,T3>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";
}

template<typename T,const size_t S>
ostream& operator<<(ostream& o,const array<T,S>& arr){
	for(int i=(o<<"[",0);i<S;++i)o<<arr[i]<<(i+1<S?",":"");
	return o<<"]\n";
}

template<typename T>
ostream& operator<<(ostream& o,const vector<T>& vec){
	for(int i=(o<<"[",0);i<vec.size();++i)o<<vec[i]<<(i+1<vec.size()?",":"");
	return o<<"]\n";
}

constexpr int M = 2e5+5, mod = 998244353;// 1e9+7;
constexpr double pi = acos(-1), eps = 1e-9;

void solve(){
	int n,m;
	cin>>n>>m;
	vector<array<int,2>> a(m);
	for(auto& [l,r]:a)cin>>l>>r,--l,--r;
	ranges::sort(a);
	vector<int> ans(n*2);
	for(auto& i:ans|views::take(n))i=1;
	vector<int> t(n*2+1);
	auto add=[&](int x,int y){
		for(;x<=n*2;x+=x&-x)t[x]+=y;
	};
	auto sum=[&](int x){
		int res=0;
		for(;x;x^=x&-x)res+=t[x];
		return res;
	};
	int cur=n-1;
	for(auto& [l,r]:a|views::reverse){
//		cout<<l<<" "<<r<<" "<<cur<<" "<<ans;
		if(cur>=l)break;
		int cnt=sum(r+1)-sum(l);
//		cout<<cnt<<" "<<l<<" "<<r<<" "<<cur<<" "<<ans;
		if(cnt)continue;
		ans[cur--]=0;
		ans[l]=1;
		add(l+1,1);
		if(l-cur-1>cur+1){
			cout<<"-1\n";
			return;
		}
	}
	for(auto i:ans)cout<<")("[i];
	cout<<"\n";
	
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t{1};
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

K Maximum GCD

分类讨论。

全局加。把原数组变成差分数组，那么通过控制x的值，gcd必定能取到后面所有项的gcd。

非全局加，a1和an至少有一个不变。只讨论a1不变的情况，an类似。gcd必定为a1的一个因子，对每个因子，从b2到bn，统计不是该因子倍数的数量，若数量不多于1，或不多于2且元素和是因子的倍数，就合法。

三者取max。

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 2; i <= n; ++i) b[i] = a[i] - a[i - 1];
    // for (int i = 2; i <= n; ++i) cout << b[i] << " \n"[i == n];
    {
        int all_same = 1;
        for (int i = 1; i < n; ++i) if (a[i + 1] != a[i]) {
            all_same = 0;
            break;
        }
        if (all_same) {
            cout << "0\n";
            return;
        }
    }
    int ans = 0;
    for (int i = 2; i <= n; ++i) ans = gcd(ans, b[i]);
    // debug(ans);
    auto calc = [&](int l, int r, int v) -> int {
        vector<int> d;
        for (int i = 1; i * i <= v; ++i) {
            if (v % i == 0) {
                d.push_back(i);
                if (i * i != v) d.push_back(v / i);
            }
        }
        ranges::sort(d, greater<int>());
        // vector<int> b(r - l + 1);
        // b[0] = a[l];
        // for (int i = l + 1; i <= r; ++i) {
        //     b[i - l] = a[i] - a[i - 1]; 
        // }
        // for (int x : b) cout << x << " ";
        // cout << endl;
        for (auto x : d) {
            i64 ans = 0;
            int cnt = 0;
            for (int v : b) {
                ans += v;
                if (v % x) cnt++;
            }
            if (cnt <= 1) return x;
            if (ans % x == 0 && cnt <= 2) return x;
        }
        return 1;
    };
    ans = max(ans, calc(2, n, a[1]));
    ans = max(ans, calc(1, n - 1, a[n]));
    cout << ans << "\n";
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

D Beautiful Matrix

不会组合数学。战败了。

/*

This code template was updated by Yukii_P on 2025/4/4.

優しさ　怖くて　目をふせて触れたよ

古傷に忍び込んで　今日を忘れるよ

月明かりは二人の距離を近づけ

朝日は残酷な現実を突きつける

生まれ変わって会いに行けば

千切れた心も癒せるかな

誰かに操られていたのさ

作り物の羽に酔ったのさ

あの日に戻れたらいいのにな

あの日に戻れたらいいのにな

前世と来世に挟まれて

一方通行の道は続く

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 5e5 + 10;
constexpr int MOD = 998244353;

i64 ksm(i64 a, i64 b) {
    i64 res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void solve() {
    int n, m;
    cin >> n >> m;
    i64 fz = 1, fm = 1;
    int X = n * (n - 1) % MOD;
    {
        for (int i = 1; i <= m; ++i) {
            fz = fz * (X + i) % MOD;
            fm *= i;
            fm %= MOD;
        }
    }
    cout << fz * ksm(fm, MOD - 2) % MOD << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

E Array

序列和值域双分块，按照散对散、散对整、整对散、整对整的贡献大力分讨。

/*

This code template was updated by Yukii_P on 2025/8/9.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

template<typename T> void chkmin(T& a, T b) { a = min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = max(a, b); }
template<typename T, size_t S>
ostream& operator<<(ostream& o, array<T, S>& x) { for (int i = (o << "[", 0); i < S; ++i) o << x[i] << (i + 1 < x.size() ? ", " : ""); return o << "]";}
template<typename T>
ostream& operator<<(ostream& o, vector<T>& x) { for (int i = (o << "[", 0); i < x.size(); ++i) o << x[i] << (i + 1 < x.size() ? ", " : ""); return o << "]";}

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = ", dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2> 
void dbg2(T x, T2... args) { std::cerr << ", " << x; dbg2(args...); }
template<typename T, typename... T2> 
void dbg1(T x, T2... args) { std::cerr << x; dbg2(args...); }
template<typename T> 
void dbg1(std::vector<T> x, int s) { s = std::min<int>(s, x.size()); for (int i = (std::cerr << "[", 0); i < s; ++i) std::cerr << x[i] << (i + 1 < s ? ", " : "]\n"); }
#else
#define debug(...) 
#endif

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 330;
constexpr int MOD = 998244353;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n), p(n), bi(n), nxt(n);
    vector<i64> g(N);
    vector<vector<int>> ip(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        p[i]--;
        ip[p[i]].push_back(i);
    }
    for (int i = n - 1, t = n; i >= 0; --i) {
        nxt[i] = t;
        if (ip[i].size()) t = i;
    }
    vector<int> st;
    for (int i = 0; i < n; ) {
        int j = i + 1, cur = ip[i].size();
        while (j < n && cur + ip[j].size() < N) {
            cur += ip[j].size();
            j++;
        }
        for (int k = i; k < j; ++k) bi[k] = st.size();
        st.push_back(i);
        i = j;
    }
    int cnt = st.size();
    st.push_back(n);
    vector<vector<i64>> f(cnt, vector<i64>(N));
    vector<i64> b(cnt);
    for (int i = 0; i < n; ++i) {
        f[bi[p[i]]][i / N]++;
    }
    for (int i = 0; i < cnt; ++i) {
        for (int j = 1; j < N; ++j) {
            f[i][j] += f[i][j - 1];
        }
    }
    for (i64 op, l, r, x, lastAns = 0; q; --q) {
        cin >> op >> l >> r;
        l ^= lastAns;
        r ^= lastAns;
        l--; r--;
        if (op == 1) {
            cin >> x;
            x ^= lastAns;
            int lb = l == 0 ? 0 : bi[l - 1] + 1;
            int rb = r == n - 1 ? cnt - 1 : bi[r + 1] - 1;
            for (int i = lb; i <= rb; ++i) b[i] += x;
            vector<pii> lr;
            if (lb <= rb) {
                lr.push_back({l, st[lb] - 1});
                lr.push_back({st[rb + 1], r});
            } else {
                lr.push_back({l, r});
            }
            for (auto [l, r] : lr) {
                for (int i = l; i <= r; i = nxt[i]) {
                    a[i] += x;
                    for (int u : ip[i]) {
                        g[u / N] += x;
                    }
                }
            }
        } else {
            i64 ans = 0;
            if (r - l <= 2 * N) {
                for (int i = l; i <= r; ++i) ans += a[p[i]] + b[bi[p[i]]];
            } else {
                // 整块[lb, rb)
                int lb = l / N + 1, rb = r / N;
                for (int i = l; i < lb * N; ++i) ans += a[p[i]] + b[bi[p[i]]];
                for (int i = rb * N; i <= r; ++i) ans += a[p[i]] + b[bi[p[i]]];
                for (int i = lb; i < rb; ++i) ans += g[i];
                for (int i = 0; i < cnt; ++i) ans += b[i] * (f[i][rb - 1] - f[i][lb - 1]);
            }
            cout << ans << "\n";
            lastAns = ans;
        }
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/