AT題選做

AGC020C. Median Sum

記原序列的總和為 \(S\)

容易發(fā)現(xiàn)如果把空集也考慮進(jìn)去的話，在左邊任取一個(gè)子集，其和為 \(x\)，那么一定可以在右邊找到一個(gè)子集滿足它的和為 \(S - x\)。也就是說(shuō)，位于權(quán)值為 \(\frac{S}{2}\) 的左右兩邊的子集是對(duì)稱的。

于是，我們就能推出我們需要求的中位數(shù)就是總和超過(guò) \(\frac{S}{2}\) 的第一個(gè)子集，但直接做 01 背包的話復(fù)雜度會(huì)炸

我們可以使用 bitset 來(lái)加速一下即可

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

const int MX = 2005;
const int M = MX*MX;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    rep(i, n) cin >> a[i];

    int s = 0;
    rep(i, n) s += a[i];

    bitset<M> dp;
    dp[0] = 1;
    rep(i, n) dp |= dp<<a[i];

    for (int i = (s+1)/2; i < M; ++i) {
        if (dp[i]) {
            cout << i << '\n';
            return 0;
        }
    }

    return 0;
}

AGC030D. Inversion Sum

線性期望 + 概率轉(zhuǎn)移
把“對(duì)所有 \(2^Q\) 種操作方式求最終逆序?qū)?shù)之和”問(wèn)題轉(zhuǎn)化為先算每一對(duì)位置 \(i,j\) 最終成為逆序（即位置 \(i\) 的值大于位置 \(j\) 的值）的期望次數(shù)，最后把期望乘以 \(2^Q\) 得到“和”。

記 dp[i][j] 表示在當(dāng)前已處理的前 \(t\) 個(gè)操作之后，位置 \(i\) 的值嚴(yán)格大于位置 \(j\) 的概率。初始化時(shí)沒(méi)有隨機(jī)操作，dp[i][j] 是一個(gè) 0/1 值：

dp[i][j] = (a[i] > a[j]) ? 1 : 0;

處理一次可選交換 (x,y) 的轉(zhuǎn)移

對(duì)于某個(gè)操作對(duì) \((x,y)\)，我們有 1/2 概率交換位置 \(x\) 和 \(y\)、1/2 不交換。考慮任意位置 \(i\)：

比較 (x,i)：如果不交換，概率為老的 dp[x][i]；如果交換，位置 \(x\) 上的是原來(lái) \(y\) 的值，比較結(jié)果為老的 dp[y][i]。因此新的概率是兩者的平均：

\[dp_{\text{new}}[x][i] = \frac{dp_{\text{old}}[x][i] + dp_{\text{old}}[y][i]}{2}. \]
同理 (i,x)：

\[dp_{\text{new}}[i][x] = \frac{dp_{\text{old}}[i][x] + dp_{\text{old}}[i][y]}{2}. \]
對(duì)于 (x,y) 本身：不交換時(shí)比較結(jié)果仍是 dp[x][y]；交換時(shí)位置 \(x\) 與 \(y\) 的值對(duì)調(diào)，比較 \(x>y\) 在交換情況下等價(jià)于原來(lái)的 dp[y][x]。因此

\[dp_{\text{new}}[x][y] = \frac{dp_{\text{old}}[x][y] + dp_{\text{old}}[y][x]}{2}. \]

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using mint = modint1000000007;

int main() {
    int n, q;
    cin >> n >> q;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    vector dp(n, vector<mint>(n));
    rep(i, n)rep(j, n) dp[i][j] = a[i] > a[j];
    mint inv2 = mint(2).inv();
    
    rep(qi, q) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        
        vector<mint> lx(n), rx(n);
        vector<mint> ly(n), ry(n);
        rep(i, n) lx[i] = dp[x][i];
        rep(i, n) rx[i] = dp[i][x];
        rep(i, n) ly[i] = dp[y][i];
        rep(i, n) ry[i] = dp[i][y];
        rep(i, n) {
            dp[x][i] = dp[y][i] = (lx[i]+ly[i])*inv2;
            dp[i][x] = dp[i][y] = (rx[i]+ry[i])*inv2;
        }
        dp[x][y] = dp[y][x] = (lx[y]+ly[x])*inv2;
    }
    
    mint ans;
    rep(j, n)rep(i, j) ans += dp[i][j];
    ans *= mint(2).pow(q);
    cout << ans.val() << '\n';
    
    return 0;
}

AGC044B. Joker

按順序從點(diǎn) \(P_i\) 出發(fā)跑 \(\mathrm{bfs}\)

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using P = pair<int, int>;

inline void chmin(int& a, int b) { if (a > b) a = b; }

const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};

int main() {
    int n;
    cin >> n;
    
    vector d(n, vector<int>(n));
    rep(i, n)rep(j, n) {
        d[i][j] = i;
        chmin(d[i][j], j);
        chmin(d[i][j], n-1-i);
        chmin(d[i][j], n-1-j);
    }
    vector a(n, vector<int>(n, 1));
    
    int ans = 0;
    rep(ni, n*n) {
        int num;
        cin >> num;
        --num;
        int si = num/n, sj = num%n;
        ans += d[si][sj];
        a[si][sj]--;
        queue<P> q;
        q.emplace(si, sj);
        while (q.size()) {
            auto [i, j] = q.front(); q.pop();
            int nd = d[i][j]+a[i][j];
            rep(v, 4) {
                int ni = i+di[v], nj = j+dj[v];
                if (ni < 0 or nj < 0 or ni >= n or nj >= n) continue;
                if (d[ni][nj] <= nd) continue;
                d[ni][nj] = nd;
                q.emplace(ni, nj);
            }
        }
    }
    
    cout << ans << '\n';
    
    return 0;
}

ARC101. Median of Medians

二分答案
假設(shè)答案為 \(x\)
求滿足中位數(shù) \(\geqslant x\) 的區(qū)間數(shù)至少有 \(\left\lceil \dfrac{\frac{n(n+1)}{2}}{2} \right\rceil\) 個(gè)的 \(x\) 的最大值

其中求“中位數(shù) \(\geqslant x\) 的區(qū)間數(shù)”就是 P3031

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    int ac = 0, wa = 1001001001;
    while (abs(ac-wa) > 1) {
        int wj = (ac+wa)/2;
        
        auto ok = [&]{
            ll cnt = 0;
            fenwick_tree<int> t(2*n+1);
            int x = 0;
            t.add(n, 1);
            rep(i, n) {
                if (a[i] >= wj) x++;
                else x--;
                cnt += t.sum(0, n+x+1);
                t.add(n+x, 1);
            }
            return cnt*2 >= n*ll(n+1)/2;
        }();
        
        (ok ? ac : wa) = wj;
    }
    
    cout << ac << '\n';
    
    return 0;
}

ARC117C. Tricolor Pyramid

打表發(fā)現(xiàn)是 \((-a-b) \bmod 3\)，所以只要計(jì)算組合數(shù) \(\bmod 3\)，如果 \(n\) 是
偶數(shù)，再乘上 \(-1\) 即可。
因?yàn)檫@里是小模數(shù)，用 \(\mathrm{lucas}\) 算組合數(shù)會(huì)比較方便。

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

const int mod = 3;
//const int mod = 998244353;
//const int mod = 1000000007;
struct mint {
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod) {}
    mint operator-() const {
        return mint(-x);
    }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        return mint(*this) += a;
    }
    mint operator-(const mint a) const {
        return mint(*this) -= a;
    }
    mint operator*(const mint a) const {
        return mint(*this) *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return *this *= a.inv();
    }
    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }
};
istream& operator>>(istream& is, mint& a) {
    return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
    return os << a.x;
}

struct modinv {
  int n; vector<mint> d;
  modinv(): n(2), d({0,1}) {}
  mint operator()(int i) {
    while (n <= i) d.push_back(-d[mod%n]*(mod/n)), ++n;
    return d[i];
  }
  mint operator[](int i) const { return d[i];}
} invs;
struct modfact {
  int n; vector<mint> d;
  modfact(): n(2), d({1,1}) {}
  mint operator()(int i) {
    while (n <= i) d.push_back(d.back()*n), ++n;
    return d[i];
  }
  mint operator[](int i) const { return d[i];}
} facts;
struct modfactinv {
  int n; vector<mint> d;
  modfactinv(): n(2), d({1,1}) {}
  mint operator()(int i) {
    while (n <= i) d.push_back(d.back()*invs(n)), ++n;
    return d[i];
  }
  mint operator[](int i) const { return d[i];}
} ifacts;
mint comb(int n, int k) {
  if (n < k || k < 0) return 0;
  return facts(n)*ifacts(k)*ifacts(n-k);
}

mint lucas(int n, int k) {
  if (n == 0 && k == 0) return 1;
  mint res = comb(n%3, k%3);
  return res*lucas(n/3, k/3);
}

int main() {
    int n;
    string s;
    cin >> n >> s;
    
    string t = "BWR";
    mint ans;
    rep(i, n) {
        int x = 0;
        while (t[x] != s[i]) ++x;
        ans += lucas(n-1, i)*x;
    }
    if (n%2 == 0) ans = -ans;
    
    cout << t[ans.x] << '\n';
    
    return 0;
}

ARC160. Power Up

記 dp[i][j] 對(duì)數(shù)字 \(1, 2, \cdots, i\) 進(jìn)行操作，生成 \(j\) 個(gè) \(i+1\)
然后用后綴和優(yōu)化一下即可

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using mint = modint998244353;

int main() {
	int n;
	cin >> n;
	
	const int M = 200055;
	vector<int> c(M);
	rep(i, n) {
	    int a;
	    cin >> a;
	    c[a]++;
	}
	
	vector<mint> dp(1, 1);
	rep(a, M) {
	    int x = c[a];
	    vector<mint> p(((int)dp.size()+x)/2+1);
	    swap(dp, p);
	    rep(i, p.size()) {
	        int nx = x+i;
	        dp[nx/2] += p[i];
	    }
	    for (int i = (int)dp.size()-2; i >= 0; --i) dp[i] += dp[i+1];
	}
	
	mint ans = dp[0];
	cout << ans.val() << '\n';
	
	return 0;
}

ABC058D. ###

\( \sum\limits_{1 \leqslant i<j \leqslant n} (x_j-x_i) \times \sum\limits_{1 \leqslant k<l \leqslant n} (x_l-x_k) \)

只考慮第一項(xiàng)，第二項(xiàng)同理

\( \begin{aligned} \sum\limits_{1 \leqslant i<j \leqslant n} (x_j-x_i) &= \sum_{i=1}^n\sum_{j=i+1}^n (x_j - x_i)\\ &= \sum_{i=1}^n\sum_{j=i+1}^n x_j - \sum_{i=1}^n\sum_{j=i+1}^n x_i\\ &= \sum_{j=2}^n\sum_{i=1}^{j-1} x_j - \sum_{i=1}^n (n-i)x_i\\ &= \sum_{i=2}^n (i-1)x_i - \sum_{i=1}^n (n-i)x_i\\ &= \sum\limits_{i=1}^n (i-1 - (n-i)) x_i \end{aligned} \)

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using mint = modint1000000007;

mint f(int n) {
    mint res;
    rep(i, n) {
        int x;
        cin >> x;
        res += mint(x)*(i-(n-i-1));
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    mint x = f(n);
    mint y = f(m);
    
    mint ans = x*y;
    cout << ans.val() << '\n';
    
    return 0;
}

ABC127E. Cell Distance

所以，\(x\) 和 \(y\) 可以分別單獨(dú)考慮
這里僅討論 \(x\) 的貢獻(xiàn)，\(y\) 是類似的

\( \begin{aligned} \displaystyle \sum_{\text{所有的放法}}\sum_i\sum_j |x_i - x_j| &= \sum_i\sum_j\sum_{\text{所有的放法}} |x_i - x_j|\\ &= \sum_i\sum_j |x_i-x_j| \times {}_{nm-2}C_{k-2}\\ &= {}_{nm-2}C_{k-2} \sum_i\sum_j |x_i - x_j|\\ &= {}_{nm-2}C_{k-2} \sum_{d=0}^{n-1} d \times (n-d) \times m \times m \end{aligned} \)

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using mint = modint1000000007;

struct modinv {
  int n; vector<mint> d;
  modinv(): n(2), d({0,1}) {}
  mint operator()(int i) {
    while (n <= i) d.push_back(-d[mint::mod()%n]*(mint::mod()/n)), ++n;
    return d[i];
  }
  mint operator[](int i) const { return d[i];}
} invs;
struct modfact {
  int n; vector<mint> d;
  modfact(): n(2), d({1,1}) {}
  mint operator()(int i) {
    while (n <= i) d.push_back(d.back()*n), ++n;
    return d[i];
  }
  mint operator[](int i) const { return d[i];}
} facts;
struct modfactinv {
  int n; vector<mint> d;
  modfactinv(): n(2), d({1,1}) {}
  mint operator()(int i) {
    while (n <= i) d.push_back(d.back()*invs(n)), ++n;
    return d[i];
  }
  mint operator[](int i) const { return d[i];}
} ifacts;
mint comb(int n, int k) {
  if (n < k || k < 0) return 0;
  return facts(n)*ifacts(k)*ifacts(n-k);
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    
    mint ans;
    rep(i, n) ans += mint(i)*(n-i)*m*m;
    rep(j, m) ans += mint(j)*(m-j)*n*n;
    ans *= comb(n*m-2, k-2);
    cout << ans.val() << '\n';
    
    return 0;
}

ABC130F. Enclosed Points

本題的核心在于轉(zhuǎn)化計(jì)數(shù)對(duì)象！
不要直接計(jì)算集合 \(T\)，而是轉(zhuǎn)為統(tǒng)計(jì)“點(diǎn) \(P\) 被計(jì)數(shù)的次數(shù)”的總和！

這樣一來(lái)，問(wèn)題就拆解為：

"\(T\) 包含點(diǎn) \(P\) 時(shí)，其他點(diǎn)任意選" 的 \(2^{N-1}\) 種情況
\(T\) 不包含點(diǎn) \(P\) 時(shí)，只有 \(T\) 斜跨這個(gè)點(diǎn)對(duì)應(yīng)的一三象限或二四象限時(shí)滿足。可以先用掃描線求出點(diǎn) \(P\) 的四個(gè)象限上包含的點(diǎn)數(shù)，然后通過(guò)容斥解決。

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using P = pair<int, int>;
using mint = modint998244353;

mint f(int a, int b, int c, int d) {
    mint res;
    vector<int> num = {a, b, c, d};
    vector<mint> o(4), ox(4);
    rep(i, 4) {
        ox[i] = mint(2).pow(num[i]);
        o[i] = ox[i]-1;
    }
    res += ox[0]*o[1]*o[2]*ox[3];
    res += o[0]*ox[1]*ox[2]*o[3];
    res -= o[0]*o[1]*o[2]*o[3];
    
    res += ox[0]*ox[1]*ox[2]*ox[3];
    return res;
}

int main() {
    int n;
    cin >> n;
    
    vector<P> ps(n);
    rep(i, n) cin >> ps[i].first >> ps[i].second;
    
    { // compress x
        map<int, int> mp;
        rep(i, n) mp[ps[i].first] = 0;
        int j = 0;
        for (auto&& x : mp) x.second = j++;
        rep(i, n) ps[i].first = mp[ps[i].first];
    }
    { // compress y
        map<int, int> mp;
        rep(i, n) mp[ps[i].second] = 0;
        int j = 0;
        for (auto&& x : mp) x.second = j++;
        rep(i, n) ps[i].second = mp[ps[i].second];
    }
    
    ranges::sort(ps);
    
    vector<int> a(n), b(n), c(n), d(n);
    rep(_, 2) {
        { // calc a, b
            fenwick_tree<int> t(n);
            rep(i, n) {
                a[i] = t.sum(0, ps[i].second);
                b[i] = i-a[i];
                t.add(ps[i].second, 1);
            }
        }
        ranges::reverse(ps);
        swap(a, c);
        swap(b, d);
        ranges::reverse(a);
        ranges::reverse(b);
        ranges::reverse(c);
        ranges::reverse(d);
    }
    
    mint ans;
    rep(i, n) {
        ans += f(a[i], b[i], c[i], d[i]);
    }
    
    cout << ans.val() << '\n';
    
    return 0;
}

ABC149F. Surrounded Nodes

枚舉包含在內(nèi)部的白點(diǎn)，直接求包含這個(gè)點(diǎn)的最小連通塊是困難的
但我們可以求它不包含在內(nèi)部的最小連通塊的個(gè)數(shù)
假設(shè)點(diǎn) \(v\) 是包含在內(nèi)部的白點(diǎn)，考察以點(diǎn) \(v\) 為根的所有子樹(shù)
全部染色數(shù)\((2^{N-1})\) \(-\) 都染白色 \((1)\) \(-\) 只有一個(gè)子樹(shù)有黑點(diǎn)\((\sum (2^{T_{c_i}}-1))\)

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using mint = modint1000000007;

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> to(n);
    rep(i, n-1) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    
    mint ans;
    auto dfs = [&](auto& f, int v, int p=-1) -> int {
        int res = 1;
        vector<int> ts;
        for (int u : to[v]) {
            if (u == p) continue;
            int t = f(f, u, v);
            res += t;
            ts.push_back(t);
        }
        if (p != -1) {
            ts.push_back(n-res);
        }
        mint now = mint(2).pow(n-1)-1;
        for (int t : ts) {
            now -= mint(2).pow(t)-1;
        }
        ans += now;
        return res;
    };
    dfs(dfs, 0);
    ans /= mint(2).pow(n);
    
    cout << ans.val() << '\n';
    
    return 0;
}

ABC204F. Hanjo 2

狀壓dp+矩陣快速冪

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;
using mint = modint998244353;

template<typename T>
struct Matrix {
  int h, w;
  vector<vector<T>> d;
  Matrix() {}
  Matrix(int h, int w, T val=0): h(h), w(w), d(h, vector<T>(w,val)) {}
  Matrix& unit() {
    assert(h == w);
    rep(i,h) d[i][i] = 1;
    return *this;
  }
  const vector<T>& operator[](int i) const { return d[i];}
  vector<T>& operator[](int i) { return d[i];}
  Matrix operator*(const Matrix& a) const {
    assert(w == a.h);
    Matrix r(h, a.w);
    rep(i,h)rep(k,w)rep(j,a.w) {
      r[i][j] += d[i][k]*a[k][j];
    }
    return r;
  }
  Matrix pow(long long t) const {
    assert(h == w);
    if (!t) return Matrix(h,h).unit();
    if (t == 1) return *this;
    Matrix r = pow(t>>1);
    r = r*r;
    if (t&1) r = r*(*this);
    return r;
  }
};

int main() {
    int h; ll w;
    cin >> h >> w;
    
    int n = 1<<h;
    Matrix<mint> d(n, n);
    
    rep(s, n) {
        rep(x, n) { // x集合：沒(méi)有被左邊一列占用的行
            if (x&s) continue; 
            for (int y = x;; y = (y-1)&x) { // y集合：選哪些行橫著放2*1
                int ns = 0;
                rep(i, h) {
                    if (x>>i&1) {
                        if (y>>i&1) { // 橫著放
                            ns |= 1<<i; // 向右延伸一格
                        }
                        else { // 豎著放
                            if (i == h-1) { ns = -1; break; }
                            if (s>>i>>1&1) { ns = -1; break; } // i+1已被左邊占用
                            if (x>>i>>1&1) { ns = -1; break; } // i+1沒(méi)在x中，沒(méi)法配對(duì)
                        }
                    }
                }
                if (ns != -1) {
                    d[s][ns] += 1;
                }
                if (!y) break;
            }
        }
    }
    
    Matrix<mint> x(n, 1);
    x[0][0] = 1;
    x = d.pow(w)*x;
    mint ans = x[0][0];
    cout << ans.val() << '\n';
    
    return 0;
}

ABC223H. Xor Query

前綴線性基的板題
對(duì)于每一位上的基底，盡可能掛越靠右的數(shù)

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

const int D = 60;
template<typename T>
struct MaxBasis {
    vector<T> d;
    vector<int> w;
    MaxBasis(): d(D), w(D) {}
    void add(T x, int nw) {
        rep(i, D) if (x>>i&1) {
            if (d[i]) {
                if (nw > w[i]) swap(d[i], x), swap(w[i], nw);
                x ^= d[i];
            }
            else {
                d[i] = x;
                w[i] = nw;
                break;
            }
        }
    }
    bool solve(int l, ll x) {
        rep(i, D) if (x>>i&1) {
            if (w[i] >= l) x ^= d[i];
        }
        return x == 0;
    }
};

struct Q {
    int i, l; ll x;
    Q(int i, int l, ll x): i(i), l(l), x(x) {}
};

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    
    int n, q;
    cin >> n >> q;
    
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
   
    vector<vector<Q>> qs(n);
    rep(qi, q) {
        int l, r; ll x;
        cin >> l >> r >> x;
        --l; --r;
        qs[r].emplace_back(qi, l, x);
    }
    
    MaxBasis<ll> mb;
    vector<bool> ans(q);
    rep(i, n) {
        mb.add(a[i], i);
        for (auto [qi, l, x] : qs[i]) {
            ans[qi] = mb.solve(l, x);
        }
    }
    
    rep(i, q) {
        if (ans[i]) puts("Yes");
        else puts("No");
    }
    
    return 0;
}

ABC229G. Longest Y

雙指針

先預(yù)處理出每個(gè) Y 左邊有多少個(gè) .，對(duì)于一段區(qū)間將所有的 Y 交換到一起意味著讓區(qū)間里每個(gè) Y 處左邊的 . 數(shù)相同，而 “讓區(qū)間里每個(gè) Y 處左邊的 . 數(shù)相同”的最小操作次數(shù)是個(gè)經(jīng)典問(wèn)題，就是 LC462。然后預(yù)處理一下 . 數(shù)序列的前綴和就可以做到 \(O(1)\) 判定。

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    string s; ll k;
    cin >> s >> k;
    int n = s.size();
    
    vector<int> a;
    rep(i, n) if (s[i] == 'Y') a.push_back(i-a.size());
    n = a.size();
    vector<ll> d(n+1);
    rep(i, n) d[i+1] = d[i]+a[i];
    
    int ans = 0;
    int r = 0;
    rep(l, n) {
        while (r < n) {
            int nr = r+1;
            int c = (l+nr)/2;
            ll now = ll(c-l)*a[c] - (d[c]-d[l]);
            now += (d[nr]-d[c]) - ll(nr-c)*a[c];
            if (now > k) break;
            r = nr;
        }
        ans = max(ans, r-l);
    }
    
    cout << ans << '\n';
    
    return 0;
}

ABC230F. Predilection

原題可以理解成對(duì)原序列劃分成若干段，接著分別對(duì)每段求和，就得到了一個(gè)新的序列 \(B\)，問(wèn)能生成多少種本質(zhì)不同的序列 \(B\)

可以發(fā)現(xiàn)每次操作，原序列的前綴和序列 \(S\) 中都會(huì)少一個(gè)數(shù)（顯然不會(huì)刪掉 \(S_0\) 和 \(S_n\)），那么本題就轉(zhuǎn)化成了有多少個(gè)本質(zhì)不同的序列 \((S_1, S_2, \cdots, S_{n-1})\) 的子序列，而這個(gè)問(wèn)題是經(jīng)典的dp題。

記 dp[i] 表示最后取的是數(shù)字 \(S_i\) 的本質(zhì)不同的子序列個(gè)數(shù)

轉(zhuǎn)移方程：

\( \displaystyle dp[i] = \sum_{j \leqslant i-1} [S_i \ \text{上一次出現(xiàn)的位置} \leqslant j] \ dp[j] \)

可以用 map 來(lái)維護(hù) \(S_i\) 上一次出現(xiàn)的位置

這樣一來(lái)時(shí)間復(fù)雜度就是 \(\mathcal{O}(n^2)\)

下面考慮進(jìn)行優(yōu)化：

可以考慮容斥

\( \displaystyle dp[i+1] = dp[i] + (dp[i] - dp[\operatorname{last}[S_i]]) \)

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;
using mint = modint998244353;

int main() {
    int n;
    cin >> n;
    
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    vector<ll> s(n+1);
    rep(i, n) s[i+1] = s[i]+a[i];
    s.erase(s.begin());
    s.pop_back();
    n--;
    
    mint ans = 1;
    map<ll, mint> dp;
    rep(i, n) {
        mint tmp = ans;
        ans += ans-dp[s[i]];
        dp[s[i]] = tmp;
    }
    
    cout << ans.val() << '\n';
    
    return 0;
}

ABC230G. GCD Permutation

記 \(f(A)\) 表示從 \(A\) 中任選兩個(gè)數(shù)不互素的二元組的個(gè)數(shù)
那么答案就是 \(\sum\limits_{k=2}^n f(P_{ki})\mu'(k)\)，這里的 \(P_{ki}\) 指由 \(P\) 中所有下標(biāo)為 \(k\) 的倍數(shù)的數(shù)構(gòu)成的子序列，\(\mu(k) = -\mu(k)\)

\(f(A) = \sum\limits_{k=2}^n \mu'(k) \times \text{能被}\, k \, \text{整除的} \, A_i \, 的數(shù)中任選兩個(gè)數(shù)（可以兩個(gè)都選同一個(gè)數(shù)）的方案數(shù)\)

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;
using P = pair<int, int>;

struct Sieve {
	int n;
	vector<int> f, primes;
	Sieve(int n=1): n(n), f(n+1) {
		f[0] = f[1] = -1;
		for (ll i = 2; i <= n; ++i) {
			if (f[i]) continue;
			primes.push_back(i);
			f[i] = i;
			for (ll j = i*i; j <= n; j += i) {
				if (!f[j]) f[j] = i;
			}
		}
	}
	vector<int> factorList(int x) {
		vector<int> res;
		while (x != 1) {
			res.push_back(f[x]);
			x /= f[x];
		}
		return res;
	}
	vector<P> factor(int x) {
		vector<int> fl = factorList(x);
		if (fl.size() == 0) return {};
		vector<P> res(1, P(fl[0], 0));
		for (int p : fl) {
			if (res.back().first == p) {
				res.back().second++;
			}
			else {
				res.emplace_back(p, 1);
			}
		}
		return res;
	}
	vector<int> divisors2(int x) {
	    auto ps = factor(x);
	    vector<int> res{1};
	    for (auto [p, _] : ps) {
	        for (int i = res.size()-1; i >= 0; --i) {
	            res.push_back(res[i]*p);
	        }
	    }
	    res.erase(res.begin());
	    return res;
	}
};

ll c2(ll n) { return n*(n+1)/2; }

int main() {
    int n;
    cin >> n;
    
    Sieve prime(n);
    
    vector<int> a(n+1);
    rep(i, n) cin >> a[i+1];
    
    vector<int> mu(n+1, -1);
    mu[1] = 0;
    for (int p : prime.primes) {
        for (int i = p; i <= n; i += p) mu[i] = -mu[i];
        for (ll i = (ll)p*p; i <= n; i += (ll)p*p) mu[i] = 0;
    }
    
    vector<vector<int>> ds(n+1);
    for (int i = 1; i <= n; ++i) {
        ds[i] = prime.divisors2(i);
    }
    
    ll ans = 0;
    for (int k = 2; k <= n; ++k) {
        if (mu[k] == 0) continue;
        ll now = 0;
        unordered_map<int, int> s;
        for (int i = k; i <= n; i += k) {
            for (int x : ds[a[i]]) s[x]++;
        }
        for (auto [j, cnt] : s) now += c2(cnt)*mu[j];
        ans += now*mu[k];
    }
    
    cout << ans << '\n';
    
    return 0;
}

ABC233F. Swap and Sort

原題其實(shí)就是給定一張 \(N\) 個(gè)點(diǎn) \(M\) 條邊的圖，頂點(diǎn) \(i\) 上放有棋子 \(P_i\) 。一條邊直接相連的兩端點(diǎn)可以交換其上放置的棋子。問(wèn)是否能讓棋子 \(p_i\) 落在點(diǎn) \(i\) 上。對(duì)于樹(shù)的情況比較簡(jiǎn)單，可以從葉子節(jié)點(diǎn) \(V\) 開(kāi)始搜，在整棵樹(shù)上找是否有哪個(gè)點(diǎn)上放有棋子 \(v\)，如果找到了的話，那么這個(gè)葉節(jié)點(diǎn)及其和它父親相連的邊就可以不考慮了。那么對(duì)于一般圖的話，只需考慮每個(gè)連通塊的生成樹(shù)即可。

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)

struct Edge {
    int to, id;
    Edge(int to, int id): to(to), id(id) {}
};

int main() {
    int n;
    cin >> n;
    
    vector<int> P(n);
    rep(i, n) cin >> P[i];
    rep(i, n) P[i]--;
    
    int m;
    cin >> m;
    dsu uf(n);
    vector<vector<Edge>> g(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        if (uf.same(a, b)) continue;
        uf.merge(a, b);
        g[a].emplace_back(b, i+1);
        g[b].emplace_back(a, i+1);
    }
    
    vector<int> ans;
    rep(sv, n) if (uf.leader(sv) == sv) {
        auto get = [&](auto& f, int v, int tg, int p=-1) -> bool {
            if (P[v] == tg) return true;
            for (auto [u, id] : g[v]) {
                if (u == p) continue;
                if (f(f, u, tg, v)) {
                    ans.push_back(id);
                    swap(P[v], P[u]);
                    return true;
                }
            }
            return false;
        }; 
        auto dfs = [&](auto& f, int v, int p=-1) -> void {
            for (auto [u, id] : g[v]) {
                if (u == p) continue;
                f(f, u, v);
            }
            if (!get(get, v, v)) {
                puts("-1");
                exit(0);
            }
        };
        dfs(dfs, sv);
    }
    
    cout << ans.size() << '\n';
    for (int i : ans) cout << i << ' ';
    
    return 0;
}

ABC233G. Strongest Takahashi

注意到如果能用一個(gè)子矩陣，用兩個(gè)相交的子矩陣反而更劣
考慮二維區(qū)間dp
記 dp[si][sj][ti][tj] 表示摧毀左上坐標(biāo)為 \((s_i, s_j)\) 以及右下坐標(biāo)為 \((t_i-1, t_j-1)\) 的子矩陣中的所有障礙物的最小代價(jià)

代碼實(shí)現(xiàn)

#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

inline void chmin(int& x, int y) { if (x > y) x = y; }

int dp[55][55][55][55];

int main() {
    int n;
    cin >> n;
    
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    
    rep(ti, n+1)rep(si, ti)rep(tj, n+1)rep(sj, tj) {
        dp[si][sj][ti][tj] = max(ti-si, tj-sj);
    }
    rep(i, n)rep(j, n) if (s[i][j] == '.') {
        dp[i][j][i+1][j+1] = 0;
    }
    
    for (int wi = 1; wi <= n; ++wi) {
        for (int wj = 1; wj <= n; ++wj) {
            rep(si, n)rep(sj, n) {
                int ti = si+wi, tj = sj+wj;
                if (ti > n) break;
                if (tj > n) break;
                for (int k = si+1; k < ti; ++k) {
                    int now = dp[si][sj][k][tj];
                    now += dp[k][sj][ti][tj];
                    chmin(dp[si][sj][ti][tj], now);
                }
                for (int k = sj+1; k < tj; ++k) {
                    int now = dp[si][sj][ti][k];
                    now += dp[si][k][ti][tj];
                    chmin(dp[si][sj][ti][tj], now);
                }
            }
        }
    }
    
    cout << dp[0][0][n][n] << '\n';
    
    return 0;
}

ABC233H. Manhattan Christmas Tree

整體二分
先將坐標(biāo)系順時(shí)針旋轉(zhuǎn)45°，得到切比雪夫距離，接下來(lái)就是經(jīng)典的二維數(shù)點(diǎn)問(wèn)題了

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using P = pair<int, int>;

const int M = 100005;
const int MX = M*2;

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> ps(MX);
    rep(i, n) {
        int x, y;
        cin >> x >> y;
        ps[x+y].push_back(x-y+M);
    }
    
    int q;
    cin >> q;
    vector<int> a(q), b(q), k(q);
    rep(i, q) {
        int x, y;
        cin >> x >> y >> k[i];
        a[i] = x+y;
        b[i] = x-y+M;
    }
    
    vector<int> wa(q, -1), ac(q, MX);
    rep(ti, 18) {
        vector<int> num(q), wj(q);
        vector<vector<int>> qs(MX);
        rep(i, q) {
            wj[i] = (wa[i]+ac[i])/2;
            int lx = a[i]-wj[i], rx = a[i]+wj[i]+1;
            lx = max(lx, 0);
            rx = min(rx, MX-1);
            qs[lx].push_back(i);
            qs[rx].push_back(q+i);
        }
        fenwick_tree<int> d(MX);
        rep(x, MX) {
            for (int qi : qs[x]) {
                int i = qi%q;
                int sign = qi < q ? -1 : 1;
                int ly = b[i]-wj[i], ry = b[i]+wj[i]+1;
                ly = max(ly, 0);
                ry = min(ry, MX);
                num[i] += d.sum(ly, ry)*sign;
            }
            for (int y : ps[x]) d.add(y, 1);
        }
        
        rep(i, q) {
            if (num[i] >= k[i]) ac[i] = wj[i];
            else wa[i] = wj[i];
        }
    }
    
    rep(i, q) cout << ac[i] << '\n';
    
    return 0;
}

ABC235G. Gardens

先考慮條件1，就是個(gè)簡(jiǎn)單的容斥，見(jiàn) 盒子與球

再結(jié)合條件2，假設(shè)恰有 \(M\) 個(gè)花園對(duì)條件1沒(méi)有限制，方案數(shù)就是

\[f(M) = \sum_{i=0}^a {}_MC_i \times \sum_{i=0}^b {}_MC_i \times \sum_{i=0}^c {}_MC_i \]

那么最終答案就是

\[\sum_{j=0}^N (-1)^{N-j} {}_NC_j f(j) \]

這樣時(shí)間復(fù)雜度是 \(O(N^2)\)

考慮對(duì)組合數(shù)的前綴和進(jìn)行加速

記 \(f_a(M) = \sum\limits_{i=0}^a {}_MC_i\)

有遞推公式：\(f_a(M+1) = 2f_a(M) - {}_MC_{a}\)

那么我們就可以 \(O(N)\) 預(yù)處理出 \(f_a(0) \sim f_a(N)\) 了

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using mint = modint998244353;

struct modinv {
  int n; vector<mint> d;
  modinv(): n(2), d({0,1}) {}
  mint operator()(int i) {
    while (n <= i) d.push_back(-d[mint::mod()%n]*(mint::mod()/n)), ++n;
    return d[i];
  }
  mint operator[](int i) const { return d[i];}
} invs;
struct modfact {
  int n; vector<mint> d;
  modfact(): n(2), d({1,1}) {}
  mint operator()(int i) {
    while (n <= i) d.push_back(d.back()*n), ++n;
    return d[i];
  }
  mint operator[](int i) const { return d[i];}
} facts;
struct modfactinv {
  int n; vector<mint> d;
  modfactinv(): n(2), d({1,1}) {}
  mint operator()(int i) {
    while (n <= i) d.push_back(d.back()*invs(n)), ++n;
    return d[i];
  }
  mint operator[](int i) const { return d[i];}
} ifacts;
mint comb(int n, int k) {
  if (n < k || k < 0) return 0;
  return facts(n)*ifacts(k)*ifacts(n-k);
}

int main() {
    int n;
    cin >> n;
    
    vector<int> a(3);
    rep(i, 3) cin >> a[i];
    
    vector f(3, vector<mint>(n+1));
    rep(i, 3) {
        f[i][0] = 1;
        rep(j, n) {
            f[i][j+1] = f[i][j]*2;
            if (j >= a[i]) f[i][j+1] -= comb(j, a[i]);
        }
    }
    
    mint ans;
    rep(j, n+1) {
        mint now = 1;
        rep(i, 3) now *= f[i][j];
        now *= comb(n, j);
        ans = now-ans;
    }
    
    cout << ans.val() << '\n';
    
    return 0;
}

ABC249F. Ignore Operations

考慮枚舉最后一個(gè)操作 \(1\)，那么前面的操作不管是啥樣都無(wú)所謂了，我們只需考慮后面的操作，顯然應(yīng)該將后面的所有操作 \(1\) 都跳過(guò)，為了使得最終的結(jié)果最大，所以應(yīng)該盡可能跳過(guò)操作 \(2\) 中 \(y < 0\) 的操作。可以用小根堆來(lái)維護(hù)所有 \(y < 0\) 的操作 \(2\)，如果當(dāng)前堆的大小超過(guò)剩下的 \(k\)，就彈出堆中的最大值。對(duì)于枚舉最后一個(gè)操作 \(1\) 可以倒著枚舉所有操作

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<int> t(n), y(n);
    rep(i, n) cin >> t[i] >> y[i];
    
    ll ans = -1e18;
    ll sum = 0;
    priority_queue<int> q;
    for (int i = n-1; i >= 0; --i) {
        if (k < 0) break;
        if (t[i] == 1) {
            ans = max(ans, y[i]+sum);
            k--;
            if (q.size() > k) {
                sum  += q.top(); q.pop();
            }
        }
        else {
            if (y[i] >= 0) sum += y[i];
            else {
                q.push(y[i]);
                if (q.size() > k) {
                    sum  += q.top(); q.pop();
                }
            }
        }
    }
    if (k >= 0) ans = max(ans, sum);
    
    cout << ans << '\n';
	
	return 0;
}

ABC239Ex. Dice Product 2

記 dp[i] 表示由 \(M\) 通過(guò)除以若干個(gè)整數(shù) \(x\) 變成 \(i\) 的期望次數(shù)

轉(zhuǎn)移方程：\(dp[i] = 1 + \sum\limits_{j=1}^n dp[\lfloor\frac{i}{j}\rfloor] \Leftrightarrow dp[i] = \frac{N}{N-1}(1 + \sum\limits_{j=2}^n dp[\lfloor\frac{i}{j}\rfloor])\)

時(shí)間復(fù)雜度為 \(\mathcal{O}(NM)\)

注意到和 \(\lfloor\frac{i}{j}\rfloor\) 一樣的部分可以用整除分塊來(lái)優(yōu)化
用記憶化搜索實(shí)現(xiàn)，復(fù)雜度同杜教篩，為 \(O(m^{\frac{3}{4}})\)

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using mint = modint1000000007;

int main() {
    int n, m;
    cin >> n >> m;
    
    mint inv_n1 = mint(n-1).inv();
    mint cost = mint(n)/(n-1);
    
    unordered_map<int, mint> dp;
    auto f = [&](auto& f, int x) -> mint {
        if (x == 0) return 0;
        if (dp.count(x)) return dp[x];
        mint res;
        for (int i = n; i > 1;) {
            int a = x/i;
            int ni = x/(a+1);
            res += f(f, a)*(i-ni);
            i = ni;
        }
        res *= inv_n1; res += cost;
        return dp[x] = res;
    };
    
    mint ans = f(f, m);
    cout << ans.val() << '\n';
    
    return 0;
}

ABC265G. 012 Inversion

延遲線段樹(shù)

每個(gè)點(diǎn)需要維護(hù)以下信息：

\(0/1/2\) 的個(gè)數(shù)
有序?qū)?\((0, 0)\), \((0, 1)\), \((0, 2)\)，\((1, 0)\)，\((1, 1)\)，\((1, 2)\)，\((2, 0)\)，\((2, 1)\)，\((2, 2)\) 的個(gè)數(shù)

對(duì)于操作二其實(shí)就是延遲線段樹(shù)里的映射 \(F\)

代碼實(shí)現(xiàn)

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

struct S {
    array<int, 3> c;
    array<array<ll, 3>, 3> d;
    S() {
        fill(c.begin(), c.end(), 0);
        rep(i, 3)rep(j, 3) d[i][j] = 0;
    }
};
S op(S a, S b) {
    rep(i, 3)rep(j, 3) {
        a.d[i][j] += b.d[i][j];
        a.d[i][j] += (ll)a.c[i]*b.c[j];
    }
    rep(i, 3) a.c[i] += b.c[i];
    return a;
}
S e() { return S(); }

struct F {
    array<int, 3> a;
    F(): a({0, 1, 2}) {}
};
S mapping(F f, S x) {
    S res;
    rep(i, 3)rep(j, 3) {
        res.d[f.a[i]][f.a[j]] += x.d[i][j];
    }
    rep(i, 3) res.c[f.a[i]] += x.c[i];
    return res;
}
F comp(F f2, F f1) {
    rep(i, 3) f1.a[i] = f2.a[f1.a[i]];
    return f1;
}
F id() { return F(); }

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    
    int n, q;
    cin >> n >> q;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    lazy_segtree<S, op, e, F, mapping, comp, id> t(n);
    rep(i, n) {
        S s;
        s.c[a[i]] = 1;
        t.set(i, s);
    }
    
    rep(qi, q) {
        int type, l, r;
        cin >> type >> l >> r;
        --l;
        if (type == 1) {
            S s = t.prod(l, r);
            ll ans = s.d[1][0] + s.d[2][0] + s.d[2][1];
            cout << ans << '\n';
        }
        else {
            F f;
            rep(i, 3) cin >> f.a[i];
            t.apply(l, r, f);
        }
    }
    
    return 0;
}

posted on 2024-06-07 21:43 V_Melville 閱讀(34) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部

導(dǎo)航

公告

AT題選做

AGC020C. Median Sum

AGC030D. Inversion Sum

AGC044B. Joker

ARC101. Median of Medians

ARC117C. Tricolor Pyramid

ARC160. Power Up

ABC058D. ###

ABC127E. Cell Distance

ABC130F. Enclosed Points

ABC149F. Surrounded Nodes

ABC204F. Hanjo 2

ABC223H. Xor Query

ABC229G. Longest Y

ABC230F. Predilection

ABC230G. GCD Permutation

ABC233F. Swap and Sort

ABC233G. Strongest Takahashi

ABC233H. Manhattan Christmas Tree

ABC235G. Gardens

ABC249F. Ignore Operations

ABC239Ex. Dice Product 2

ABC265G. 012 Inversion