省选模拟赛第十一轮

乘坐电梯

这不就是 poj 3539 啊

同余类最短路

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf = 1e16;

const int N = 4000010;

ll dis[N], mn, h, a, b, c, inq[N], x[3];

void spfa() {
    memset(dis, 0x3f, sizeof dis);
    queue<ll> q;
    q.push(0), inq[0] = 1, dis[0] = 0;
    while(q.size()) {
        ll x = q.front(); q.pop(); inq[x] = 0;
        for(int i = 0 ; i < 3 ; ++ i) {
            ll y = (x + :: x[i]) % mn;
            if(dis[y] > dis[x] + :: x[i]) {
                dis[y] = dis[x] + :: x[i];
                if(!inq[y]) {
                    inq[y] = 1;
                    q.push(y);
                }
            }
        }
    }
}

int main() {
    scanf("%lld%lld%lld%lld", &h, &a, &b, &c);
    h --;
    x[0] = a, x[1] = b, x[2] = c;
    sort(x, x + 3, greater<ll> ());
    mn = x[2];
    spfa();
    ll ans = 0;
    for(ll i = 0 ; i < mn ; ++ i) {
       if(dis[i] <= h) ans += (h - dis[i]) / mn + 1;
    }
    printf("%lld\n", ans);
}

Notepad--

可能出题人想让选手写平衡树……

但是他忘了有种东西叫做 rope……

%:pragma GCC optimize(2)
%:pragma GCC optimize(3)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;

int l, r, n;

char str[250010];

int main() {
    scanf("%s", str);
    rope<char> s(str);
    while(scanf("%s", str) == 1) {
        if(str[0] == 'E') break;
        else if(str[0] == 'I') {
            scanf("%s%d", str, &l);
            for(int i = 0 ; str[i] ; ++ i) {
                s.insert(i + l, str[i]);
            }
        } else if(str[0] == 'P') {
            scanf("%d%d", &l, &r);
            printf("%s\n", s.substr(l, r - l + 1).c_str());
        }
    }
}

树上求和

这不就是 Crash 的文明世界 的超级弱化版嘛……

对于每个点 $u$，维护子树到 $u$ 和非子树到 $u$ 的两个多项式

即 $\sum_{i=0}^{n}a_ix^i$，其中 $a_i$ 表示深度之和的 $i$ 次方后的结果

转移的话就是：
$$
\sum_{i=0}^{n}(a_i+s)x^i=\sum_{i=0}^{n}x^i\sum_{j=0}^{i}a_i^js^{i-j} {i \choose j}
$$
时间复杂度就是 $O(Tnk^2)$ 咯

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e4 + 10, mod = 1e9 + 7, K = 21;

int head[N], rest[N * 2], to[N * 2], tot;
void add(int u, int v) {
    to[++ tot] = v, rest[tot] = head[u], head[u] = tot;
}
int n, k; ll ans[N], C[K][K], pw[N][K];

struct POI {
    ll a[K];
    POI() { memset(a, 0, sizeof a); }
    void init(int x) { fill(a, a + k + 1, x); }
    ll &operator [] (int x) { return a[x]; }
} poi_son[N], poi_fa[N];
POI operator + (POI a, POI b) {
    for(int i = 0 ; i <= k ; ++ i)
        a[i] = (a[i] + b[i]) % mod;
    return a;
}
POI operator - (POI a, POI b) {
    for(int i = 0 ; i <= k ; ++ i)
        a[i] = (a[i] - b[i]) % mod;
    return a;
}
POI operator + (POI a, ll x) {
    for(int i = k ; i >= 0 ; -- i) {
        ll sum = 0;
        for(int j = 0 ; j <= i ; ++ j) {
            sum = (sum + a[j] * pw[x][i - j] % mod * C[i][j]) % mod;
        }
        a[i] = sum; 
    }
    return a;
}

void dfs(int u, int fa) {
    poi_son[u].init(1);
    for(int i = head[u] ; i ; i = rest[i]) {
        int v = to[i];
        if(v == fa) continue;
        dfs(v, u);
        poi_son[u] = poi_son[u] + (poi_son[v] + 1); 
    }
}

void sfd(int u, int fa) {
    if(fa) {
        poi_fa[u] = (poi_fa[fa] + 1) + (poi_son[fa] - (poi_son[u] + 1) + 1);
    }
    for(int i = head[u] ; i ; i = rest[i]) {
        int v = to[i];
        if(v == fa) continue;
        sfd(v, u);
    }
}

void sol() {
    dfs(1, 0);
    sfd(1, 0);
    for(int i = 1 ; i <= n ; ++ i) {
        ans[i] = (poi_son[i] + poi_fa[i])[k];
    }
}

int main() {
    C[0][0] = 1;
    for(int i = 1 ; i <= 20 ; ++ i) {
        C[i][0] = 1;
        for(int j = 1 ; j <= 20 ; ++ j) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        } 
    } 
    for(int i = 0 ; i <= 20000 ; ++ i) {
        pw[i][0] = 1;
        for(int j = 1 ; j <= 20 ; ++ j) {
            pw[i][j] = pw[i][j - 1] * i % mod;
        }
    }
    while(scanf("%d%d", &n, &k) == 2) {
        for(int i = 1 ; i <= n ; ++ i) head[i] = ans[i] = 0; tot = 0;
        for(int i = 1, u, v ; i < n ; ++ i) {
            scanf("%d%d", &u, &v);
            add(u, v), add(v, u);
        }
        sol();
        for(int i = 1 ; i <= n ; ++ i) printf("%lld\n", (ans[i] % mod + mod) % mod);
        puts(""); 
    } 
}