The 2021 ICPC Asia Shenyang Regional Contest

L. Perfect Matchings

标签：容斥原理，树形 $\mathrm{DP}$   

如果没有删边的限制就是组合数直接算，但是有一些边是不能选的. 

不妨考虑利用容斥原理来做，钦定选上 $\mathrm{i}$ 条树边，然后扣掉点后剩下的边随便选.     

然后这个就符合二项式反演中的公式，直接反演就能求出 $\mathrm{g[i]}$. 

这里恰好 $\mathrm{i=0}$, 所以直接上容斥的公式即可，时间复杂度是树形 $\mathrm{DP}$ 的 $\mathrm{O(n^2)}$.  

#include 
#define N  4009 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
const int mod = 998244353;    
vectorG[N];
int n, size[N], dp[N][N][2], tmp[N][2];   
// dp[x][j][0/1]: 当前为 x, 一共选了 j 对，x 是否被匹配了.       
int ADD(int x, int y) {
    return (ll)(x + y) % mod; 
}
int DEC(int x, int y) {
    return (ll)(x - y + mod) % mod; 
}
void dfs(int x, int ff) {
    size[x] = 1;    
    dp[x][0][0] = 1;    
    for(int i = 0; i < G[x].size() ; ++ i) {
        int v = G[x][i]; 
        if(v == ff) continue;   
        dfs(v, x);                  
        for(int a = 0; a <= size[x] + size[v]; ++ a) 
            tmp[a][0] = tmp[a][1] = 0;     
        for(int a = 0; a <= size[x] / 2; ++ a) {
            for(int b = 0; b <= size[v] / 2; ++ b) {
                // 前面贡献了 a, v 里面贡献了 b  
                tmp[a + b][0] = ADD(tmp[a + b][0], (ll)dp[x][a][0] * ADD(dp[v][b][0], dp[v][b][1]) % mod);     
                tmp[a + b][1] = ADD(tmp[a + b][1], (ll)dp[x][a][1] * ADD(dp[v][b][0], dp[v][b][1]) % mod);     
                tmp[a + b + 1][1] = ADD(tmp[a + b + 1][1], (ll)dp[x][a][0] * dp[v][b][0] % mod);     
            }
        }
        for(int a = 0; a <= size[x] + size[v]; ++ a) 
            dp[x][a][0] = tmp[a][0], dp[x][a][1] = tmp[a][1];  
        size[x] += size[v]; 
    }
}
int qpow(int x, int y) {
    int tmp = 1; 
    for(; y ; y >>= 1, x = (ll)x * x % mod) {
        if(y & 1) tmp = (ll)tmp * x % mod; 
    }
    return tmp;  
}
int get_inv(int x) {
    return qpow(x, mod - 2); 
}
int calc(int x) {
    // x 个对.  
    // 2 * x 个点， x 个对的方案数.  
    int tmp = 1, t2 = 1, t3 = 1;  
    for(int i = 1; i <= 2 * x; ++ i) tmp = (ll)tmp * i % mod;  
    for(int i = 1; i <= x; ++ i) t2 = (ll)t2 * i % mod;  
    for(int i = 1; i <= x; ++ i) t3 = (ll)t3 * 2 % mod;  
    return (ll)tmp * get_inv(t2) % mod * get_inv(t3) % mod; 
}
int main() {
    // setIO("input");    
    scanf("%d", &n); 
    for(int i = 1; i < 2 * n ; ++ i) {
        int x, y; 
        scanf("%d%d", &x, &y); 
        G[x].pb(y); 
        G[y].pb(x);  
    }
    dfs(1, 0);                    
    int ans = 0; 
    for(int i = 0; i <= n; ++ i) {
        int d = (i & 1) ? (mod - 1): 1;  
        ans = ADD(ans, (ll)calc(n - i) * d % mod * ADD(dp[1][i][0], dp[1][i][1]) % mod);            
    }
    printf("%d\n", ans); 
    return 0; 
}

M. String Problem

标签：字符串，后缀自动机

正式赛的时候用一个 $\mathrm{lcp}$ 乱搞切掉的，这里给出正经做法.  

遇到字典序问题，考虑利用后缀自动机来解.   

静态问题可以沿着后缀自动机的字符边贪心走大的.      

那么不妨先维护出前缀 $\mathrm{i}$ 的答案，然后考虑下一位的影响.  

显然，如果影响的话一定是下一位的字母被加入答案，那么在后缀自动机中就是答案中深度最小的点改变.   

改变成的新点一定是加入 $\mathrm{i+1}$ 字符时所影响的新点，而所有新点总和是 $\mathrm{O(n)}$ 的.

由于后缀自动机的构建方式，在线做是不现实的，不妨离线构建完后缀自动机然后记录每个点最早出现位置.  

最后开一个数组统计并离线下来即可. 

#include 
#define ll long long 
#define pb push_back
#define N  2000009  
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;   
char str[N]; 
int n, last, tot, fir[N], len[N], st[N], ch[N][26], pre[N], dep[N], vis[N], tail, a[N];   
struct data {
    int p, c;  
    data(int p = 0, int c = 0):p(p), c(c){}  
}; 
vectorG[N]; 
void extend(int c, int pos) {      
    int np = ++ tot, p = last; 
    len[np] = len[p] + 1, last = np;   
    fir[np] = pos;   
    for(; p && !ch[p][c]; p = pre[p]) {
        ch[p][c] = np;                    
    }
    if(!p) pre[np] = 1; 
    else {
        int q = ch[p][c]; 
        if(len[q] == len[p] + 1) pre[np] = q; 
        else {
            int nq = ++ tot;  
            len[nq] = len[p] + 1; 
            fir[nq] = fir[q]; 
            memcpy(ch[nq], ch[q], sizeof(ch[q]));        
            pre[nq] = pre[q], pre[np] = pre[q] = nq; 
            for(; p && ch[p][c] == q; p = pre[p]) 
                ch[p][c] = nq;  
        }
    }
}    
int main() {
    // setIO("input"); 
    scanf("%s", str + 1); 
    n = strlen(str + 1);     
    last = tot = 1; 
    for(int i = 1; i <= n ; ++ i) {    
        extend(str[i] - 'a', i);
    }  
    for(int i = 1; i <= tot; ++ i) {   
        for(int j = 0; j < 26; ++ j) {
            if(ch[i][j]) {
                int q = ch[i][j]; 
                G[fir[q]].pb(data(i, j));    
            }
        }
    }      
    vis[1] = 1, a[++ tail] = 1, st[1] = -1;       
    for(int i = 1; i <= n ; ++ i) { 
        int mk = 0, de = 0;             
        for(int j = 0; j < G[i].size() ; ++ j) {
            data e = G[i][j];                  
            if(vis[e.p] && e.c > st[e.p]) {      
                if(mk == 0) {
                    mk = e.p, de = dep[e.p]; 
                }
                else if(dep[e.p] < de) {
                    mk = e.p, de = dep[e.p];   
                }
            }
        }     
        if(mk) {
            while(a[tail] != mk) 
                vis[a[tail]] = 0, -- tail;     
            st[mk] = str[i] - 'a';    
            a[++ tail] = ch[mk][str[i] - 'a'], dep[a[tail]] = tail, vis[a[tail]] = 1, st[a[tail]] = -1;   
        }             
        printf("%d %d\n", i - tail + 2, i); 
    } 
    return 0; 
}