Problem D. Count Subtractions

想到前几天 uoj 出的那个 gcd 数论题。。。

Problem E. Kth Takoyaki Set

Humble Number?
结果居然暴力就过了。。。

#include <lastweapon/io>
using namespace lastweapon;
const int N = int(1e2) + 9;

int n, k, a[N];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    
    RD(n, k); REP(i, n) RD(a[i]);
    set<LL> s; s.insert(0);

    DO(k) {
        LL x = *s.begin(); s.erase(s.begin());
        REP(i, n) {
            LL t = x + a[i];
            s.insert(t);
        }
    }
    cout << *s.begin() << endl;
}

Problem F. Minimum Bounding Box 2

容斥原理。

一种做法是直接枚举 Bounding Box，然后容斥掉至少小一圈的情况。
这种做法要对四个边界的 2^4 种存在情况分别进行容斥。

#include <lastweapon/io>
#include <lastweapon/bitwise>
#include <lastweapon/number>
using namespace lastweapon;
const int N = int(1e6) + 9;
Int Fact[N], iFact[N];
int n, m, k;

Int Binom(int n, int m) {
    if (m < 0 || m > n) return 0;
    return Fact[n] * iFact[m] * iFact[n-m];
}

Int f(int n, int m) {
    Int z = 0; REP(s, _1(4)) {
        int a = n - _1(s, 0) - _1(s, 1); if (a <= 0) continue;
        int b = m - _1(s, 2) - _1(s, 3); if (b <= 0) continue;
        Int d = Binom(a*b, k);
        if (count_bits(s) & 1) z -= d; else z += d;
    }
    return z;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    MOD = 998244353;

    RD(n, m, k); Fact[0] = 1; REP_1(i, n*m) Fact[i] = Fact[i-1] * i; iFact[n*m] = _I(Fact[n*m]);
    DWN_1(i, n*m, 1) iFact[i-1] = iFact[i] * i;

    Int z = 0; REP_1(i, n) REP_1(j, m) z += f(i, j)*i*j*(n+1-i)*(m+1-j);
    z /= Binom(n*m, k);
    cout << z << endl;
}

更好的做法是利用期望的线性性。。单独考察每个格子。。统计它对答案的影响。。。
只要容斥掉四个角即可。

#include <lastweapon/io>
#include <lastweapon/bitwise>
#include <lastweapon/number>
using namespace lastweapon;
const int N = int(1e6) + 9;
Int Fact[N], iFact[N];
int n, m, k;

Int Binom(int n, int m) {
    if (m < 0 || m > n) return 0;
    return Fact[n] * iFact[m] * iFact[n-m];
}

Int f(int x, int y) {
    Int z = Binom(n*m, k);
    z -= Binom((x-1)*m, k) + Binom((n-x)*m, k) + Binom(n*(y-1), k) + Binom(n*(m-y), k);
    z += Binom((x-1)*(y-1), k) + Binom((x-1)*(m-y), k) + Binom((n-x)*(y-1), k) + Binom((n-x)*(m-y), k);
    return z;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    MOD = 998244353;

    RD(n, m, k); Fact[0] = 1; REP_1(i, n*m) Fact[i] = Fact[i-1] * i; iFact[n*m] = _I(Fact[n*m]);
    DWN_1(i, n*m, 1) iFact[i-1] = iFact[i] * i;

    Int z = 0; REP_1(i, n) REP_1(j, m) z += f(i, j);
    z /= Binom(n*m, k);
    cout << z << endl;
}

Posted by xiaodao
Category: 日常