day8

正睿停课

T1

上面的式子可以扩展到任意多个的情况，即：范德蒙卷积。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int mod = 998244353;
const int N = 200005;
const int Log = 18;
int f[N][19], deth[N], head[N], nxt[N << 1], to[N << 1];
int fac[N], ifac[N];
int En;
inline void add_edge(int u,int v) {
    ++En; to[En] = v; nxt[En] = head[u]; head[u] = En;
    ++En; to[En] = u; nxt[En] = head[v]; head[v] = En;
}
int ksm(int a,int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1; 
    }
    return res;
} 
inline int C(int n,int m) {
    int t1 = fac[n], t2 = ifac[n - m], t3 = ifac[m];
    return 1ll * t1 * t2 % mod * t3 % mod;
}
void init(int n) { 
    fac[0] = 1;
    for (int i=1; i<=n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[n] = ksm(fac[n], mod - 2);
    for (int i=n; i; --i) ifac[i - 1] = 1ll * ifac[i] * i % mod;
}
void dfs(int u,int fa) {
    deth[u] = deth[fa] + 1;
    for (int i=head[u]; i; i=nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        f[v][0] = u;
        dfs(v, u);
    }
}
int LCA(int u,int v) {
    int d = deth[u] - deth[v];
    for (int i=Log; i>=0; --i) 
        if ((d >> i) & 1) u = f[u][i];
    if (u == v) return u;
    for (int i=Log; i>=0; --i) 
        if (f[u][i] != f[v][i]) 
            u = f[u][i], v = f[v][i];
    return f[u][0];
}
int main() {    
    int n = read();
    init(n);
    for (int i=1; i<n; ++i) {
        int u = read(), v = read();
        add_edge(u, v);
    }
    dfs(1, 0);
    for (int j=1; j<=Log; ++j) 
        for (int i=1; i<=n; ++i)
            f[i][j] = f[f[i][j - 1]][j - 1];
    int m = read();
    for (int i=1; i<=m; ++i) {
        int u = read(), v = read(), len, ans = 0;
        if (deth[u] < deth[v]) swap(u, v);
        int lca = LCA(u, v);
        if (lca == v) {
            len = deth[u] - deth[lca];
            printf("%d\n", (ksm(ksm(2, len), mod - 2)) % mod);
        } else {
            int y = deth[u] - deth[lca], x = deth[v] - deth[lca];
//          for (int i=0; i<=x; ++i) 
//              ans = (ans + 1ll * C(x, i) * C(y, i) % mod) % mod;
            ans = C(x + y, x); 
            printf("%d\n",1ll * ans * ksm(ksm(2, x + y), mod - 2) % mod);
        }
    }
    return 0;
}
/*
3
1 2
1 3
2
3 1
3 2
5
5 4
4 1
4 3
1 2
3
3 1
5 3
5 1
*/

T2

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int p[1000005], a[10005], b[10005], dp[10005];
// dp[i] 表示大小为i的石子，双方使用最有策略的情况的，先手的步数-后手的步数
// 由于一个可以拆分的大小只能由A或者B 
// 那么对于一堆石子，如果只能由先手拆分，那么他会选择一个拆分方案最大的。
// 只能由后手拆分的时候，他会拆分所有方案中最小的
int main() {
    int n = read(), m = read();
    int tota = read();
    for (int i = 1; i <= tota; ++i) a[read()] = 1;
    int totb = read();
    for (int i = 1; i <= totb; ++i) b[read()] = 1;
    for (int i = 1; i <= n; ++i) p[i] = read();
    for (int i = 2; i <= m; ++i) {
        if (a[i]) {
            for (int j = 1; j <= i / 2; ++j) 
                dp[i] = max(dp[i], dp[i - j] + dp[j] + 1);
        }
        if (b[i]) {
            for (int j = 1; j <= i / 2; ++j) 
                dp[i] = min(dp[i], dp[i - j] + dp[j] - 1);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans += dp[p[i]];
    puts(ans > 0 ? "Pomegranate" : "Orange");
    return 0;
}
/*
2 3 1 1 1 2 1 3
3 5 2 5 4 3 1 3 2 5 1 1
5 7 3 5 3 7 2 2 6 6 4 6 6 2
*/