HourRank 20

第一题略

第二题组合数学

s1 = min(cnt['a'],cnt['b']),

s2 = min(cnt['c'],cnt['d']),

b1 = max(cnt['a'],cnt['b']),

b2 = max(cnt['c'],cnt['d']);

简单分开枚举'a','b'一组和'c','d'一组然后乘起来就好了

ans = sigma(C(s1,i) * C(b1,i))(0<=i<=s1) * sigma(C(s2,i) * C(b2,i))(0<=i<=s2) - 1;

#include<bits/stdc++.h>
#define MP make_pair
using namespace std;
typedef long long LL;
const int N = 5e5 + 5;
const LL mod = 1e9 + 7;
int Tm[333];
char s[N];
LL fac[N];
LL inv[N];
LL qpow(LL x,LL b){
    LL res = 1;
    while(b){
        if(b&1)res = res * x % mod;
        x = x * x % mod;
        b >>= 1;
    }
    return res;
}
void init(){
    fac[0] = 1;
    for(int i = 1; i < N; i++)fac[i] = fac[i-1] * i % mod;
    inv[N - 1] = qpow(fac[N - 1],mod - 2);
    for(int i = N - 2; i >= 0; i--){
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
inline LL C(int a,int b){
    return fac[a] * inv[b] % mod * inv[a - b] % mod;
}
int s1,b1,s2,b2;
LL solve(){
    LL res1 = 0,res2 = 0;
    for(int i = 0; i <= s1; i++){
        res1 = (res1 + C(s1,i) * C(b1,i) % mod) % mod;
    }
    for(int i = 0; i <= s2; i++){
        res2 = (res2 + C(s2,i) * C(b2,i) % mod) % mod;
    }
//    cout<<s1<<" "<<s2<<endl;
//    cout<<res1<<" "<<res2<<endl;
    return (res1 * res2 % mod - 1 + mod)%mod;
}
int main() {
   // freopen("input", "r", stdin);
    // freopen("input", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    int q;
    cin>>q;
    while(q--){
        memset(Tm,0,sizeof Tm);
        cin>>s;
        int len = strlen(s);
        for(int i = 0; i < len; i++)Tm[(int)s[i]]++;
        s1 = min(Tm['a'],Tm['b']);
        b1 = max(Tm['a'],Tm['b']);
        s2 = min(Tm['c'],Tm['d']);
        b2 = max(Tm['c'],Tm['d']);
        cout<<solve()<<endl;
    }
    return 0;

}

第三题对于每个询问建一颗虚树，根节点要放在虚树里，如果u , fa，fa是u的祖先，并且u到fa这条路径上只有这两个点，那这条路径的点子树黑点都等于u上的子树黑点。

#include<bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
const int N = 6e5 + 5;
const LL mod = 1e9 + 7;
int L[N];
int n;
int R[N];
int ans[N];
int Fa[N][20];
int deep[N];
int tin = 0;
vector<int>Tree[N];
vector<int>Mtree[N];
int rev[N];
bool cmp(int a, int b) {
    return L[a] < L[b];
}
int lca(int a, int b) {
    if(deep[a] < deep[b])swap(a, b);
    int d = deep[a] - deep[b];
    for(int i = 0; i < 20; i++) {
        if(d & (1 << i))a = Fa[a][i];
    }
    if(a == b)return a;
    for(int i = 19; i >= 0; i--) {
        if(Fa[a][i] != Fa[b][i])a = Fa[a][i], b = Fa[b][i];
    }
    return Fa[a][0];
}
int v[N];
int St[N];
int top = 0;
inline bool isFa(int fa,int u){
    return L[fa] <= L[u] && R[fa] >= R[u];
}
inline void dfs(int u,int fa){
    for(int to : Mtree[u]){
        dfs(to,u);
        v[u] += v[to];
    }
    ans[v[u]] += deep[u] - deep[fa];
}
inline void solve() {
    int k, x;
    cin >> k;
    int tol = 0;
    for(int i = 0; i < k; i++) {
        cin >> x;
        rev[tol++] = x;
        v[x] = 1;
    }
    sort(rev, rev + tol, cmp);
    for(int i = 1; i < k; i++) {
        rev[tol++] = lca(rev[i - 1], rev[i]);
    }
    rev[tol++] = 1;
    sort(rev, rev + tol, cmp);
    tol = unique(rev , rev + tol) - rev;
    top = 0;
    St[++top] = 1;
    for(int i = 1; i < tol; i++){
        int to = rev[i];
        while(top > 0 && !isFa(St[top],to))top--;
        int nt = St[top];
        Mtree[nt].PB(to);
        St[++top] = to;
    }
    dfs(1,0);
    ans[0] = n;
    for(int i = 1; i <= k; i++)ans[0] -= ans[i];
    for(int i = 0; i <= k; i++)cout<<ans[i]<<" ",ans[i] = 0;
    for(int i = 0; i < tol; i++){
        Mtree[rev[i]].clear();v[rev[i]] = 0;
    }
    cout<<endl;
}
void pre(int u, int fa) {
    deep[u] = deep[fa] + 1;
    L[u] = ++tin;
    Fa[u][0] = fa;
    for(int to : Tree[u]) {
        if(to == fa)continue;
        pre(to, u);
    }
    R[u] = tin;
}
void init() {
    cin>>n;
    for(int i = 1; i < n; i++) {
        int u, to;
        cin >> u >> to;
        Tree[u].PB(to), Tree[to].PB(u);
    }
    pre(1, 0);
    for(int i = 1; (1 << i) < n; i++) {
        for(int j = 1; j <= n; j++) {
            Fa[j][i] = Fa[Fa[j][i - 1]][i - 1];
        }
    }
    int q;
    cin >> q;
    while(q--) {
        solve();
    }
}
int main() {
   // freopen("input", "r", stdin);
    // freopen("input", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    return 0;
}