#9：自闭的味道——4

BZOJ1005，给了度就有prufer序，排列组合。

#include <bits/stdc++.h>
using namespace std;

struct BigInt {
    int a[10005], len;

    BigInt() {
        memset(a, 0, sizeof(a));
        len = 1;
    }

    BigInt operator * (const int p) const {
        BigInt ret = *this;
        for (int i = 1; i <= ret.len; i++) {
            ret.a[i] *= p;
        }
        for (int i = 1; i <= ret.len; i++) {
            ret.a[i+1] += ret.a[i] / 10;
            ret.a[i] %= 10;
        }
        while (ret.a[ret.len+1]) {
            ret.len++;
            ret.a[ret.len+1] += ret.a[ret.len] / 10;
            ret.a[ret.len] %= 10;
        }
        return ret;
    }

    BigInt operator / (const int p) const {
        BigInt ret = *this;
        for (int i = ret.len; i; i--) {
            ret.a[i-1] += ret.a[i] % p * 10;
            ret.a[i] /= p;
        }
        while (!ret.a[ret.len] && ret.len > 1)
            ret.len--;
        return ret;
    }
};

int n, d[1001];
int sum, cnt;
bool none;
BigInt ans;

void cal() {
    ans.a[1] = 1;
    for (int i = n-1-sum; i <= n-2; i++)
        ans = ans * i;
    for (int i = 1; i <= n; i++)
        for (int j = 2; j < d[i]; j++)
            ans = ans / j;
    for (int i = 1; i <= n-2-sum; i++)
        ans = ans * (n-cnt);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
        if (!d[i])    none = true;
        if (~d[i])    cnt++, sum += d[i]-1;
    }
    if (sum > n-2)    none = true;
    if (n == 1) {
        printf("%d
", d[1] > 0 ? 0 : 1);
        return 0;
    }
    if (none) {
        puts("0");
        return 0;
    }

    cal();
    for (int i = ans.len; i; i--)
        printf("%d", ans.a[i]);
    puts("");

    return 0;
}

BZOJ1430，顺手prufer水题一道。

#include <cstdio>
#define ll long long
#define mod 9999991

int n, ans = 1;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n-2; i++)
        ans = (ll)ans * n % mod;
    for (int i = 1; i < n; i++)
        ans = (ll)ans * i % mod;
    printf("%d
", ans);
    return 0;
}

BZOJ1008，基础的组合数学。

#include <cstdio>
#define ll long long
#define mod 100003

ll m, n;

ll ksm(ll a, ll b) {
    ll res = 1ll;
    for (; b; b >>= 1) {
        if (b & 1)    res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

int main() {
    scanf("%lld%lld", &m, &n);
    printf("%d
", (ksm(m, n) - m*ksm(m-1, n-1)%mod + mod) % mod);
    return 0;
}

然后就开始被各种DP题卡死……看不懂题解qwq

今日末开启单调队列优化的学习，POJ1821，列完式子k和j关系不大所以可以预处理一下的意思？

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m;
int f[110][16010];
int q[16010];
struct worker {
    int L, P, S;

    bool operator < (const worker b) const {
        return S < b.S;
    }
}a[110];

inline int cal(int i, int k) {
    return f[i-1][k] - a[i].P * k;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &a[i].L, &a[i].P, &a[i].S);
    sort(a+1, a+1+m);

    for (int i = 1; i <= m; i++) {
        int l = 1, r = 0;
        for (int k = max(0, a[i].S - a[i].L); k < a[i].S; k++) {
            while (l <= r && cal(i, q[r]) <= cal(i, k))
                r--;
            q[++r] = k;
        }

        for (int j = 1; j <= n; j++) {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
            if (j >= a[i].S) {
                while (l <= r && q[l] < j - a[i].L)    l++;
                if (l <= r)
                    f[i][j] = max(f[i][j], cal(i, q[l]) + a[i].P * j);
            }
        }
    }

    printf("%d
", f[m][n]);
    return 0;
}