Atcoder Beginner 246 FG EX

F - typewriter

题意：给出 $n$ 个字符串和一个长度 $L$，接下来你可以任选一个字符串，并且只用这个串内有的字符来打字（不限制字符顺序，数量），问可以打出多少中长度为 $L$ 的字符串。数据范围 $N<18$，$L<10^9$

第一种想法（没a）：可以暴力枚举所选的字符集，一共 $2^{26}$ 种情况，先预处理出每一种字符在哪些给定的串中出现（bitmask），把所选的字符集的出现位置与一下，如果与的结果不为0说明这一字符集是可选的，就加上使用这个字符集的答案。为了避免重复，还要求这个字符集内的每一个字符都必须用到。假设字符集有 $k$ 个，那么答案就是将 $L$ 个位置分配给 $k$ 个字符，每个字符必须分配到至少一个位置。

本以为这个应该是一个公式解决，但查了一下发现是第二类斯特林数，递推也要 $O(L)$，目前我没法记录这个值。

第二种做法：暴力容斥，枚举选取了哪些串，计算使用同时被这些串所拥有的字符集的答案，如果选择了奇数个串答案就加上，否则答案就减去。

ll qpow(ll x, ll p){
    ll r = 1;
    while(p > 0){
        if(p & 1) r = r * x % mode;
        x = x * x % mode;
        p /= 2;
    }
    return r;
}
int vis[27];
ll res[27], ans = 0;

void solve(){
    int n, l;
    cin >> n >> l;
    for(int i=0;i<=26;i++) res[i] = qpow(i, l);
    for(int i=1;i<=n;i++){
        string s;
        cin >> s;
        for(char c: s) vis[i] |= (1 << (c - 'a'));
    }

    for(int i=1;i<(1<<n);i++){
        int st = (1 << 26) - 1, f = -1;
        for(int k=1;k<=n;k++){
            if(i & (1 << (k-1))){
                st = st & vis[k];
                f *= -1;
            }
        }
        int cnt = 0;
        for(int k=0;k<26;k++) if(st & (1 << k)) cnt++;
        (ans += f * res[cnt]) %= mode;
    }
    cout << (ans % mode + mode) % mode << '\n';
}

G - Game on Tree 3

题意：有一棵树，每个点有权值。Alice和Bob在玩游戏，一开始Bob在树根节点上，接下来轮流行动：

• Alice选择任意一个节点，将其权值清零
• Bob选择一条相邻的边，移动到一棵子树上（不可返回）

Bob可以随时结束游戏，问Bob能走到的最大点权是多少（Alice会让这个值尽可能小）

首先二分答案，假设答案为 $k$，那么Alice就要在Bob走到任意大于 $k$ 的节点之前，清空这些节点。

再考虑树上dp，设 $dp[i]$ 表示：当Bob走到 $i$ 这个子树上后，Alice需要在这个子树上操作至少多少次才能阻止Bob

这么设置状态的原因是Alice可以提前处理一些比较远的点（在Bob目前没有威胁时）

转移时：$dp[u] = \sum dp[v]-1+(val[v]>k)$

如果 $dp[1]>1$，说明Alice无法阻止Bob，继续二分调整答案。

int n, val[maxn];
vector<int> vp[maxn];
int f[maxn];

void dfs(int p, int fa, int lim){
    f[p] = 0;
    for(int v: vp[p]){
        if(v != fa){
            dfs(v, p, lim);
            f[p] += max(0, f[v]-1) + (val[v] > lim);
        }
    }
}

void solve(){
    cin >> n;
    for(int i=2;i<=n;i++) cin >> val[i];
    for(int i=1;i<n;i++){
        int u, v;
        cin >> u >> v;
        vp[u].push_back(v);
        vp[v].push_back(u);
    }
    int l = 0, r = 1e9;
    while(l < r){
        int mid = (l + r) / 2;
        dfs(1, -1, mid);
        if(f[1] > 1){
            l = mid + 1;
        }else{
            r = mid;
        }
    }
    cout << l << '\n';
}

Ex - 01? Queries

题意：给出一个长度为 $n$ 的序列，仅包含 0,1,?，接下来有 $Q$ 次操作，每次选择一个位置，将其修改为0,1,?中的一个，然后问你：当前序列包含多少种不同的子序列，? 可以视为 0 或 1

先不考虑修改，单独对一个序列如何求解：

设 $dp[i][0/1]$ 表示前 $i$ 位上，末尾为 $0/1$ 的子序列个数，转移时：

• 若 $s[i]=0$，则 $dp[i][0]=dp[i-1][0]+dp[i-1][1]+1$，否则 $dp[i][0]=dp[i-1][0]$
• 若 $s[i]=1$，则 $dp[i][1]=dp[i-1][0]+dp[i-1][1]+1$，否则 $dp[i][1]=dp[i-1][1]$

? 则两者均成立

这种对子序列的dp没怎么见过，感觉挺玄妙的，以 $dp[i][0]=dp[i-1][0]+dp[i-1][1]+1$ 为例，我的理解的思路是：

• 先继承上一位的结果： $dp[i-1][0]$
• 然后对上一位的每一个子序列，都在末尾加上一个0，即加上：$dp[i-1][0]+dp[i-1][1]+1$（包括空串加0）
• 然后减去重复部分，显然，上述第一部分是完全被第二部分包含的，那么直接把第一部分去掉即可。

有了这个dp式子之后呢？怎么处理询问？

这个dp形式比较简单，可以考虑用矩阵来表示，还是以当前位为0举例：
$$
\left[
\begin{matrix}
dp[i-1][0] & dp[i-1][1] & 1 \
\end{matrix}
\right]
\times
\left[
\begin{matrix}
1 & 0 & 0 \
1 & 1 & 0 \
1 & 0 & 1
\end{matrix}
\right]
=
\left[
\begin{matrix}
dp[i][0] & dp[i][1] & 1 \
\end{matrix}
\right]
$$
同样可以把1和？表示成矩阵。我们要做单点修改矩阵值，查询整段矩阵乘积，可以用线段树维护。

struct mat{
    int a[3][3];
    mat operator *(const mat &t)const{
        mat res = {};
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    (res.a[i][j] += 1ll * a[i][k] * t.a[k][j] % mode) %= mode;
                }
            }
        }
        return res;
    }
};

const mat m[3] = {
        {1, 0, 0,
         1, 1, 0,
         1, 0, 1},
        {1, 1, 0,
         0, 1, 0,
         0, 1, 1},
        {1, 1, 0,
         1, 1, 0,
         1, 1, 1}
};
map<char, int> fff{{'0', 0}, {'1', 1}, {'?', 2}};

string s;
struct segTree{
    mat sum[maxn << 2];
    void push_up(int p){
        sum[p] = sum[p*2] * sum[p*2+1];
    }
    void modify(int p, int l, int r, int pos, int t){
        if(l == r){
            sum[p] = m[t];
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid) modify(p*2, l, mid, pos, t);
        else modify(p*2+1, mid+1, r, pos, t);
        push_up(p);
    }
    void build(int p, int l, int r){
        if(l == r){
            sum[p] = m[fff[s[l-1]]];
            return;
        }
        int mid = (l + r) / 2;
        build(p*2, l, mid);
        build(p*2+1, mid+1, r);
        push_up(p);
    }
}segt;

void solve(){
    int n, q;
    cin >> n >> q;
    cin >> s;
    segt.build(1, 1, n);
    for(int i=1;i<=q;i++){
        int x; char c;
        cin >> x >> c;
        segt.modify(1, 1, n, x, fff[c]);
        mat res = mat{0, 0, 1,
                      0, 0, 0,
                      0, 0, 0} * segt.sum[1];
        cout << (1ll * res.a[0][0] + res.a[0][1]) % mode << '\n';
    }
}