C

贪心

每次可以选一个子序列，全部减一。问最少多少次操作可以变成不减。

只能减不能加，那么贪心的想，最后一个元素一定不能减，否则它变小了，可能需要前面的元素减更多次才能保证序列不减。

所以处理完一个后缀 $[i,n]$ 之后, $b_{i-1}$ 一定比后缀里的所有都要小，也就是比 $b_i$ 小。如果初始 $a_{i-1}>b_i$ ，需要减小到 $b_i$ ，如果本来就比 $b_i$ 小则不用操作。

最后我们每次可以操作一个子序列，也就是同时操作多个。所以操作次数上界取决于需要操作次数最多的那个元素。

#include <bits/stdc++.h>
#define int long long


using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;


void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int Max = -INF;
    int ans = -INF;
    for (int i = 1; i <= n; i++) {
        Max = max(a[i], Max);
        ans = max(ans, Max - a[i]); 
    }
    cout << ans << "\n";
}


signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1; cin >> T;
    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}

F

倍增

每次都可以把 $a_i=|a_i-x|$ ， $x$ 任选。问操作不超过 $n$ 次，可以得到的 $\sum |a_i-a_j|$ 最小值

注意到这个操作，每次如果 $x=\frac{min+max}{2}$ ，每次都会让整个值域折半。所以很快就会所有元素变成一样的，或者只有 $0,1$ 两种值

最多 $O(\log n)$ 次就收敛了，所以直接暴力模拟 $30$ 次左右。此时的数组一定已经收敛了

扫描线计算答案即可

#include <bits/stdc++.h>
#define int long long

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int MOD = 998244353;
constexpr ll INF = 1E18;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int Max = *max_element(1 + a.begin(), a.end());
    int Min = *min_element(1 + a.begin(), a.end());
    int cnt = 0;
    int Time = 35;
    while (cnt < min(Time, n)) {
        int v = (Min + Max) / 2;
        for (int i = 1; i <= n; i++) {
            a[i] = abs(a[i] - v);
        }
        Max = *max_element(1 + a.begin(), a.end());
        Min = *min_element(1 + a.begin(), a.end());
        cnt++;
    }
    sort(1 + a.begin(), a.end());
    vector<int> pre(n + 1);
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        // cout << a[i] << " " << pre[i] << endl;
        ans += ((a[i] * i % MOD - pre[i]) % MOD + MOD) % MOD;
        ans %= MOD;
    }
    // cout << endl;
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1;
    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}

I

矩阵快速幂优化dp

alt

表达式求值问题，不用考虑运算优先级。显然是无后效性的，一般可以考虑dp，只要算出来前缀的值就行。

这个 $dp$ ，先考虑加法和乘法。这很常规，假设前缀不同表达式个数为 $cnt$ ，加法就是给每个都加当前数， $sum=sum+cnt*x$ 。乘法则是给所有前缀都乘上 $x$ ， $sum=sum*x$

比较麻烦的是还有位运算。但是 $x<=10$ ，所以位运算只会影响到低 $4$ 位。可以增加状态，记录低 $4$ 的 $mask$ ，就能算出来位运算的影响。比如按位与，就是高位丢弃掉，低位变成mask & x，按位与和按位异或，都是高位不变，低位变成mask^x,mask|x

这需要我们维护低位为 $mask$ 的方案数。这并不困难，就是状压 $dp$ 记录方案素的思路，当前 $mask$ 会转移到运算后的新 $mask$ ，需要注意的是，五种运算，都会带来 $mask$ 的变化，不要漏了+,*，而且这两种运算后， $mask$ 可能超过四位，需要截取低四位。

最后 $n$ 很大，需要矩阵快速幂优化 $dp$ 。我们需要把这个 $dp$ 转移，转成矩阵表示。如果我们采用矩阵左乘状态向量的话，状态向量需要是个列向量，并且矩阵里 $a_{ij}=c$ ，表示 $dp_i+=c*dp_j$ 这个转移，不要搞反行列。

void solve()
{
    int n,k;
    cin>>n>>k;
     
    vi a(k);
    for(auto &x:a){
        cin>>x;
    }
    int all=(1<<4);
    int sum=16,cnt=17;
    Matrix f(2+all,vi(2+all));
    for(int i:a){
        f[sum][sum]+=i;
        f[sum][cnt]+=i;
        f[sum][sum]++;
         
        for(int mask=0;mask<all;mask++){
            f[i&mask][mask]++;
            f[i|mask][mask]++;
            f[i^mask][mask]++;
            f[sum][mask]+=(i&mask);
            f[sum][mask]+=((i|mask)-mask);
            f[sum][mask]+=((i^mask)-mask);
             
            f[(i+mask)&(all-1)][mask]++;
            f[(i*mask)&(all-1)][mask]++;
        }
        f[sum][sum]+=2;
        f[cnt][cnt]+=5;
    }
     
    rep(i,0,2+all-1){
//      cout<<i<<":";
        rep(j,0,2+all-1){
            f[i][j]=(f[i][j]%M2+M2)%M2;
//          cout<<f[i][j]<<' ';
        }
//      cout<<'\n';
    }
     
    Matrix f0(2+all,vi(1));
    for(int i:a){
        f0[sum][0]+=i;
        f0[cnt][0]++;
        f0[i][0]++;
    }
     
    Matrix g=power(f,n-1,M2);
    Matrix res=multiply(g,f0,M2);
     
//  rep(i,0,17){
//      cout<<i<<' '<<res[i][0]<<'\n';
//  }
    int ans=res[sum][0];
//  cout<<ans<<' ';
    ans=ans*inv(res[cnt][0],M2)%M2;
    cout<<ans<<'\n';
}

J

数论，求 $gcd(a^b,c^d),a,b,c,d=1e18$

太大了。一种思路是分解 $a,c$ 质因子，然后每个因子的指数取 $min$ 。最后知道 $gcd$ 的每个因子，再用快速幂或者欧拉降幂来计算

这样需要快速分解 $1e18$ 大小的数。考虑 $pollard rho$ 。但还是太慢了，多测会寄。

实际上 $pollard rho$ 在这里就是个暴力的错解。正解是数学，很快。

alt

么此都可以把 $gcd$ 提出来，求 $gcd$ 是个下降很快的，最多 $\log V$ 次就会降低到 $1$ ，所以递归 $O(\log V)$ 层，每层算一下 $gcd$ 。总复杂度 $O(\log^2V)$

25暑期第七场

C

F

I

J