牛客多校第九场题解

C - Cells

题意： 给出二维坐标上个点，对于第个点要到达，只能向下走或者向右走，求路线不相交的方案总数。

题解：

• 考虑引理，引理可以用于在上求解不相交路径方案数问题
• 表示这条路径上的边权之积,解决路径计数问题时通常设为
• 表示到的每一条路径上的值之和

• 答案就是矩阵的行列式

代入本题，答案就为

则
对于每一列，我们都乘，这样最后的行列式就扩大了,
然后我们利用初等列变换将前一列消掉靠后的列，可以得到
可以发现这是个范德蒙德行列式，可得行列式为$j!\prod_{1 \leq i < j \leq n}(a_j - a_i)n^2NTTn\log{n}$

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

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e7 + 10;
const int maxm = 1e5 + 10;
const int mod = 998244353;

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
ll qpow(ll n,ll k,ll mod) {ll ans=1;while(k){if(k&1)ans=ans*n%mod;n=n*n%mod;k>>=1;}return ans%mod;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n, c[maxn], a[maxn], b[maxn];
ll limit, rev[maxn], lim;

inline void NTT(ll *F, int type){
    for(int i = 0; i < limit; i++)
        if(i < rev[i]) swap(F[i], F[rev[i]]);
    for(int mid = 1; mid < limit; mid <<= 1){
        int Wn=qpow(3,type==1?(mod-1)/(mid<<1):(mod-1-(mod-1)/(mid<<1)), mod);
        for(int r = mid << 1, j = 0; j < limit; j += r){
            int w = 1;
            for(int k = 0; k < mid; k++, w = 1ll * w * Wn % mod){
                int x = F[j + k], y = 1ll * w * F[j + mid + k] % mod;
                F[j + k] = (x + y) % mod, F[j + mid + k] = (x - y + mod) % mod;
            } 
        }
    }
    if(type == -1){
        int inv = qpow(limit, mod-2, mod);
        for(int i = 0; i < limit; i++) F[i] = 1ll * F[i] * inv % mod;
    }
}

inline void work(ll *a,ll *b){
    NTT(a, 1); NTT(b, 1);
    for(int i = 0; i < limit; i++) a[i] = 1ll * a[i] * b[i] % mod;
    NTT(a, -1);
}

void solve(){
    scanf("%lld", &n);
    ll ans1 = 1;
    ll ans2 = 1, base = 1;
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &c[i]);
        ans1 = (c[i] + 1) * ans1 % mod;
        base = base * i % mod;
        ans2 = ans2 * qpow(base, mod - 2, mod) % mod;
    }
    for(int i = 1; i <= n; i++)
        a[c[i] + 1000000] = 1;
    for(int i = 1; i <= n; i++)
        b[1000000 - c[i]] = 1;
    int len = 3000000;
    limit = 1, lim = 0;
    while(limit <= len) limit <<= 1, ++lim;
    for(int i = 0; i < limit; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lim - 1));
    work(a, b);
    ll ans = 1;
    for(int i = 2000001; i <= 3000000; i++) {
        if(a[i]) {
            // dbg(a[i], i);
            ans = ans * qpow(i - 2000000, a[i], mod) % mod;
        }
    }
    // dbg(ans, ans1, ans2);
    printf("%lld\n", ans * ans1 % mod * ans2 % mod);
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt", "w", stdout);
    int t = 1;
    // t = rd();
    // scanf("%d", &t);
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

E - Eyjafjalla

题意：
一棵有根树，父节点的温度一定大于子节点，每次询问一个节点，给定一个温度区间，若相邻节点的温度在这个区间内，就可以进去，问最多能去几个节点。

思路：
根据温度关系，我们可以先往上找到最后一个祖先节点，使得其温度小于等于询问的右区间，那么接下来我们只需要找其儿子下有多少个节点的温度大于等于询问的区间就行了。

找祖先可以通过倍增来找。一下子询问子树中有多少个节点的温度大于等于一个值，尝试根据序建树。因为存在多个子树的询问，每个子树都是独立的，建立主席树来维护。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dbg(x...) do{ cerr << #x << " -> "; err(x);} while (0)
void err() { cerr << endl;}
template<class T, class... Ts> void err(const T& arg, const Ts&... args) { cerr << arg << " "; err(args...);}
const int N = 1e5 + 7;
const int M = 1e9 + 1;
vector<int> G[N];
int stt[N], fnt[N], par[N][20], w[N], dfsId;
int n, rt[N], to[N];

void dfsOd(int u, int fa) {
    par[u][0] = fa;
    for (int i = 1; i < 20; ++i) {
        par[u][i] = par[ par[u][i - 1] ][i - 1];
    }
    stt[u] = ++dfsId;
    to[dfsId] = u;
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfsOd(v, u);
    }
    fnt[u] = dfsId;
}

struct Seg {
    struct Node {
        int ls, rs, cnt;
        void init() {
            ls = rs = cnt = 0;
        }
    }t[N * 200];

    int tot;
    void init() {
        tot = 0;
        t[tot].init();
    }

    int newnode() {
        t[++tot].init();
        return tot;
    }
    void build(int &id, int l, int r) {
        if (!id) id = newnode();
        if (l == r) return;
        int mid = l + r >> 1;
        build(t[id].ls, l, mid);
        build(t[id].rs, mid + 1, r);
    }
    void modify(int &rt, int l, int r, int pos, int v) {
        int now = newnode();
        t[now] = t[rt];
        t[now].cnt += v;
        if (l == r) {
            rt = now;
            return;
        }
        int mid = l + r >> 1;
        if (pos <= mid) {
            modify(t[now].ls, l, mid, pos, v);
        } else {
            modify(t[now].rs, mid + 1, r, pos, v);
        }
        rt = now;
    }
    int query(int lr, int rr, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr) return t[rr].cnt - t[lr].cnt;
        int res = 0;
        int mid = l + r >> 1;
        if (ql <= mid) res += query(t[lr].ls, t[rr].ls, l, mid, ql, qr);
        if (qr > mid) res += query(t[lr].rs, t[rr].rs, mid + 1, r, ql, qr);
        return res;
    }
}seg;

void run() {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &w[i]);
    }
    seg.init();
    dfsOd(1, 0);
    for (int i = 1; i <= n; ++i) {
        rt[i] = rt[i - 1];
        seg.modify(rt[i], 1, M, w[to[i]], 1);
    }
    int q;
    scanf("%d", &q);
    int u, l, r;
    w[0] = 0x3f3f3f3f;
    while (q--) {
        scanf("%d %d %d", &u, &l, &r);
        if (w[u] < l || w[u] > r) {
            puts("0");
            continue;
        }
        for (int i = 19; i >= 0; --i) {
            if (w[ par[u][i] ] <= r) u = par[u][i];
        }
        printf("%d\n", seg.query(rt[stt[u] - 1], rt[fnt[u]], 1, M, l, r));
    }
}

int main() {
    int t = 1;
    while (t--) run();
    return 0;
}

G - Glass Balls

题意：

• 给出一颗根为的树，每个节点上刚开始都有一个球向它的父亲滚动，一个球在一个单位的时间内只能滚一条边。
• 存在一种特殊的节点，这种节点出现的概率为，一旦有球滚到这个节点，这个球就被拿出这棵树。
• 存在一种特殊的情况，当两个球滚到同一个节点，不论这个节点是否特殊，整个系统就会崩溃掉，并且你得到的分数为。
• 定义为刚开始在第个节点上的球滚过的边数，定义分数为，求期望的分数

题解： 首先需要找到这题的突破口，那就是要先找到使系统不崩溃的概率。显然的是，要想系统不崩溃，对于一个父节点来说，若它有个子节点，那这个子节点中至少要有个特殊节点，所以系统不崩溃的概率为$size_u - 1size_udp_{son} = 1 + dp_{fa}sonfason$

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

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define tint tuple<int, int, int> 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-8;
const int maxn = 5e5 + 10;
const int maxm = 1e5 + 10;
const int mod = 998244353;

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
ll qpow(ll n,ll k,ll mod) {ll ans=1;while(k){if(k&1)ans=ans*n%mod;n=n*n%mod;k>>=1;}return ans%mod;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, p;
vector<int> G[maxn];
ll dp[maxn];

void dfs(int now, int fa) {
    for(auto g : G[now]) {
        ll tmp = (1 - p + mod) * qpow(p, G[now].size() - 1, mod) % mod;
        tmp = tmp * qpow((G[now].size() * (1 - p + mod) % mod * qpow(p, G[now].size() - 1, mod) % mod + qpow(p, G[now].size(), mod)) % mod, mod - 2, mod) % mod;
        dp[g] = (1 + dp[now]) * tmp % mod;
        dfs(g, now);
    }
}

void solve() {
    scanf("%d %d", &n, &p);
    for(int i = 2, x; i <= n; i++) {
        scanf("%d", &x);
        G[x].eb(i);
    }

    ll P = 1;
    for(int i = 1; i <= n; i++) {
        ll sz = G[i].size();
        if(sz == 0) continue;
        P = P * (sz % mod * (1 - p + mod) % mod * qpow(p, sz - 1, mod) % mod + qpow(p, sz, mod)) % mod;
    }
    dfs(1, 0);
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ans = (ans + dp[i]) % mod;
    }
    ans = ans * P % mod;
    pt(ans);
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt", "w", stdout);
    int t = 1;
    // t = rd();
    // scanf("%d", &t);
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

H - Happy Number

题解： 签到题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dbg(x...) do{ cerr << #x << " -> "; err(x);} while (0)
void err() { cerr << endl;}
template<class T, class... Ts> void err(const T& arg, const Ts&... args) { cerr << arg << " "; err(args...);}
const int maxn = 1e5 + 7;

int n; 
string s;
char ch[10] = {"623"};

void run() {
    cin >> n;
    while(n) {
//        dbg(n, ch[n % 3]);
        s += ch[n % 3];
        if(n % 3 == 0) n--;
        n /= 3;
    }
    reverse(s.begin(), s.end());
    cout << s << endl;
}

int main() {
    int t = 1;
//    scanf("%d", &t);
    while (t--) run();
    return 0;
}

I - Incentive Model

题意： 有两人一起逐个挖块矿，对于同一块矿，有的概率属于,有的概率属于,其中为两方当时的股权占比。某方拥有一块矿后，其股权增加。初始有的股权，有的股权。求能获得矿的期望数量

题解： 令为第块矿挖出后的股权，所以获得第块股权的概率为
所以$\frac{S_i - a}{w} = aiwans = \frac{nx}{y}$

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

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-8;
const int maxn = 5e3 + 10;
const int maxm = 1e5 + 10;
const int mod = 998244353;

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
ll qpow(ll n,ll k,ll mod) {ll ans=1;while(k){if(k&1)ans=ans*n%mod;n=n*n%mod;k>>=1;}return ans%mod;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n, x, y, w;

void solve() {
    scanf("%lld %lld %lld %lld", &n, &w, &x, &y);
    ll ans = n * x % mod * qpow(y, mod - 2, mod) % mod;
    pt(ans);
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt", "w", stdout);
    int t = 1;
    // t = rd();
    // scanf("%d", &t);
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

J - Jam

题意： 每辆车需要花费一秒钟通过十字路口，通过分配每秒钟十字路口上的红绿灯情况，用最少的时间通过十字路口上的所有车辆。

思路：

• 关于右转，任何路口上的任何方向都不会对某一路口上的右转产生影响，因此可以一直放行。
• 剩下四个路口一共八种方向，枚举后发现，同一时刻最多可以有两个绿灯
  • 同一路口的左转和直走同时放行
  • 当前路口的直走和左边路口的左转
  • 当前路口的直走和对面路口的直走
  • 当前路口的左转和对面路口的左转
  • 当前路口的左转和右边路口的右转
• 由此联想到，让哪两个方向在同一时刻上一起放行，就变成了一个匹配问题

把所有方向，一分为二， 分别放到左右两个点集。根据上面分析的内容对左右两个点集进行建边。最后一个源点连接左边所有点，一个汇点连接右边所有点，跑出的网络流答案除以二即为可以同时间一起放行的时间长度。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 30;

int cnt, head[maxn];
struct edge {
    int v, w, next;
    edge() {}
    edge(int v, int w, int next) : v(v), w(w), next(next) {}
} e[maxn * maxn * 2];

void add(int u, int v, int w) {
    e[++cnt] = edge(v, w, head[u]), head[u] = cnt;
    e[++cnt] = edge(u, 0, head[v]), head[v] = cnt;
}

int s, t;
void init() {
    cnt = 1, s = 20, t = 21;
    memset(head, 0, sizeof head);
}

int cur[maxn];
int dep[maxn];
bool bfs() {
    memset(dep, 0, sizeof dep);

    queue<int> Q;
    Q.emplace(s);
    dep[s] = 1;

    while (Q.size()) {
        int u = Q.front();
        Q.pop();
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v, w = e[i].w;
            if (dep[v] == 0 && w > 0) {
                dep[v] = dep[u] + 1;
                Q.emplace(v);
            }
        }
    }
    return dep[t] > 0;
}

int dfs(int u, int flow) {
    if (u == t) return flow;
    for (int& i = cur[u]; i; i = e[i].next) {
        int v = e[i].v, w = e[i].w;
        if (dep[v] == dep[u] + 1 && w) {
            int minflow = dfs(v, min(flow, w));
            if (minflow > 0) {
                e[i].w -= minflow;
                e[i ^ 1].w += minflow;
                return minflow;
            }
        }
    }
    return 0;
}

int Dinic() {
    int ans = 0;
    while (bfs()) {
        for (int i = 1; i <= t; ++i) cur[i] = head[i];
        while (int d = dfs(s, inf)) ans += d;
    }
    return ans / 2;
}

int d[] = {0, 3, 4, 1, 2};
int l[] = {0, 2, 3, 4, 1};
int r[] = {0, 4, 1, 2, 3};

int c[5][5];
void run() {
    init();

    for (int i = 1; i <= 4; ++i) {
        for (int j = 1; j <= 4; ++j) {
            scanf("%d", c[i] + j);
        }
    }

    int sum = 0;
    int ans = 0;
    for (int i = 1; i <= 4; ++i) {
        add(s, i * 2 - 1, c[i][d[i]]);
        add(s, i * 2 - 0, c[i][l[i]]);

        add(i * 2 + 7, t, c[i][d[i]]);
        add(i * 2 + 8, t, c[i][l[i]]);

        add(i * 2 - 1, i * 2 + 8, inf);
        add(i * 2 - 1, l[i] * 2 + 8, inf);
        add(i * 2 - 1, d[i] * 2 + 7, inf);

        add(i * 2, i * 2 + 7, inf);
        add(i * 2, r[i] * 2 + 7, inf);
        add(i * 2, d[i] * 2 + 8, inf);

        sum += c[i][d[i]] + c[i][l[i]];
        ans = max(ans, c[i][r[i]]);
    }

    printf("%d\n", max(ans, sum - Dinic()));
}

int main() {
    int _ = 1;

    scanf("%d", &_);
    while (_--) run();

    return 0;
}