中值定理

模型：如果一个序列 \(a\) 长度为 \(p\)，\(a_1 = 0, a_p = 1\)，需要找到一个长度为 \(q\) 的子序列 \(a[l, r]\) 使得 \(a_l = 0, a_r = 1\)，且 \(q|p\)，那么可以这样考虑：对于 \([a_1,a_q],[a_{q+1},a_{2q}],[a_{2q+1},a_{3q}]...\) 一定存在至少一个序列满足条件。这是个可以二分的结构。二分的时候以 \(q\) 为单位长度，令 \(mid = kq\)，若 \(a_{mid}=1\)，那么继续在 \(a[l,mid]\) 上二分。否则在 \([mid+1,r]\) 上二分。

UER #11 B

【题意】给定一个长度为 \(2n-1\) 的序列，要求拿出其中的 \(n\) 个数，使得它们加起来是 \(n\) 的倍数。
\(n \le 5 \times 10^5\)
【分析】
令命题 \(EGF(n)\) 表示对于任意数组 \(n\) 都符合题意并且找到了一个构造方法。

若 \(n\) 为合数，不妨设 \(n=pq\)。假设 \(EGF(p) \and EGF(q)\)，那么考虑首先对 \(n\) 不断取前 \(2p-1\) 个数，然后找出 \(p\) 个符合条件的数合并成一个 \(p\) 的倍数，再将其他数丢回去，直到剩下的数没有 \(2p-1\) 个为止。注意到 \(2n-1=2pq-1=(2q-2)p+(2p-1)\)，因此可以找出 \((2q-1)\) 个 \(p\) 的倍数，剩下可以扔掉。然后对这些数做 \(EGF(q)\) 就得到了一组合法解。因此只需要考虑素数情形。

素数怎么办。考虑 \(EGF(p)\)。考虑对这 \(2p-1\) 个数采用不断选众数和第二多的数的方式，分成 \(p-1\) 个二元组和一个剩下来的数，其中每个二元组都满足其中两个数不一样。

我们选上这个数。另外选上每个二元组第一个数。得到一个 \(p\) 个数的选择方案，加起来为 \(k\)。我们的问题转化为了，有 \(p\) 个数 \(d_1,...,d_p\)（第二个数与第一个数的差），选出一个子集满足加起来模 \(p\) 余 \(-k\)。

先考虑证明一定存在一种选法。我们归纳地证明。

假设前 \(i\) 个数选出的子集和可以表出的数集合为 \(S_i\)。定义集合 \(S_i + k\) 表示 \(\{a+k|a\in S_i\}\)。那么考虑证明：\(k \not \equiv 0(\bmod p)\) 并且 \(S_i\) 不是 \(p\) 的完全剩余系的情况下 \(S_i \neq S_i+k\)。

这个怎么证，反证法。假设成立，那么考虑 \(x \in S_i, y \not \in S_i\) 有：\(x+k \in S_i, x+2k \in S_i,...\)，但是我们令 \(j = (y-x) \times k^{-1}\)，有 \(x+jk=y \in S_i\)，矛盾。因此原命题成立。

这个命题代表了什么？\(S_i\) 不是 \(p\) 的完全剩余系的情况下 \(|S_i \cup (S_i+k)| > S_i\)！因此对于 \(S_0 = {0}\)，\(S_n\) 一定是 \(p\) 的完全剩余系，因为每次会增长至少 \(1\) 个数。

我们考虑构造答案。首先我们让每次增长恰好 \(1\) 个数，则比较容易记录答案。暴力增长是 \(O(n^2)\) 的。我们考虑采用中值定理优化。

首先我们有个非常巧妙的观察：若 \(xk \in S_i, (x+1)k \not \in S_i\)，那么一定可以将 \((x+1)k\) 放进去！并且你可以找到一个 \((u,v)\) 使得 \(uk \in S_i, vk \not \in S_i\)。因此可以直接中值定理二分，\(q=1\)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
//调不出来给我对拍！
int a[700010];
bitset<300000> bs;
vector<int> v[300100];
set<pii> s;
pair<int, int> p;
int nsum = 0;
vector<int> ts;
vector<int> pre;
vector<int> add;
int tim[300100];
int ch[300100];
int n; 
int inv[300100];
int qpow(int x, int k) {
    int ans = 1;
    while(k) {
        if(k & 1) ans = ans * x % n;
        x = x * x % n;
        k >>= 1;
    }
    return ans;
}
int bin(int i, int j, int d) {
    int l = i * inv[d]; int r = j * inv[d] - 1;
    while(r < l) r += n;
    while(l < r) {  
        int mid = (l + r + 1) >> 1;
        if(!bs[mid * d % n]){r = mid - 1; }
        else { l = mid; }
    }
    return (r + 1) * d % n;
}
set<int> cp, uc;  //选了，没选  
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    cin >> n;
    f(i, 1, n - 1) inv[i] = qpow(i, n - 2); 
    f(i, 1, 2 * n - 1) cin >> a[i];
    f(i, 1, 2 * n - 1) a[i] %= n;
    f(i, 1, 2 * n - 1) { v[a[i]].push_back(i); }
    f(i, 0, n - 1) { if(v[i].size() >= n) {f(j, 0, n - 1) {cout << v[i][j] << " ";} cout << endl; return 0;}}
    f(i, 0, n - 1) { s.insert({v[i].size(), i}); }
    ts.push_back(0); pre.push_back(0);
    f(i, 1, n - 1) {
        pii cur = (*(--s.end())); s.erase(--s.end());
        pii urc = (*(--s.end())); s.erase(--s.end());
    //    cout << cur.second << " " << urc.second << endl;
        nsum += cur.second; ch[cur.second] ++; nsum %= n; 
        ts.push_back((urc.second - cur.second + n) % n); pre.push_back(cur.second);
        if(cur.first > 1) {s.insert({cur.first - 1, cur.second});}
        if(urc.first > 1) {s.insert({urc.first - 1, urc.second});} 
    }
    pii nct = (*(--s.end()));// cout << nct.second << endl; //assert(s.size() == 1);
    nsum += nct.second; ch[nct.second] ++; nsum %= n; //cout << nsum << endl;
    int tar = (n - nsum) % n;

 //   cout << tar << endl;
    bs[0] = 1; tim[0] = 0;
    cp.insert(0); f(i, 1, n - 1) uc.insert(i);
    int now = 1;
    while(!bs[tar]) {
  //  f(i, 0, 3) {   
        int t = bin((*(cp.begin())), (*(uc.begin())), ts[now]);
        uc.erase(t); cp.insert(t);
        bs[t] = 1; tim[t] = now;
        
     //   cout <<"add : "<< t << endl;
     //   tim[t] = now; 
        now++;
 //   }
    }

    int ncp = tar; int ccp = tim[ncp];
    while(1) {
        if(ccp <= 0) break;
     //   cout << ncp << " " << ccp << endl;
        ch[pre[ccp]] --; ch[(pre[ccp] + ts[ccp]) % n] ++;
        ncp = (ncp - ts[ccp] + n) % n; ccp = tim[ncp];
    }
    f(i, 0, n - 1) { f(j, 0, ch[i] - 1) cout << v[i][j] << " ";}
    cout << endl;
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}

[WC2023] 楼梯

也可以用中值定理优化 \(O(n^2)\) 的找区间子区间的过程，但是这题直接保证了 \(q|p\)。