A、Browser Games

题目大意

给出个字符串，你需要输出行。

对于第个字符串来说，你需要在这些字符串里面分别找到一个前缀，并且满足这些前缀去重之后长度最小。

其次就是你曾经选择过的前缀不能做为前缀出现在这些字符串里面。

卡了空间只允许。

Solution

考点：字符串hash

如果是正序的话比较容易考虑到字典树，但是字典树的空间这题卡空间过不去。

我们倒序的思考，对于最后一个字符串，只需要考虑前字符串里面第一个字符出现了几种就是答案了。

那么接下来如何处理加入的第个字符串。

我们把第个字符串的全部前缀都出来，接下来去一个里面把相同的前缀出现过的下标全部找出来，并且让这些下标在的位置前缀长度即可。然后处理完之后把第个字符串的前缀全部删掉，因为你已经有了它前缀的新字符串了。

这样一路往前递推就可以在的时间内完成这一系列操作。

const int N = 1e5 + 7, bas = 131;

ull p[N];
unordered_map<ull, vector<int>> mp;
int pos[N], ans[N];
string s[N];

int solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        pos[i] = 0;
        p[i] = s[i][0];
        mp[p[i]].push_back(i);
    }

    for (int i = n; i >= 1; --i) {
        ans[i] = mp.size();
        ull pre = 0;
        for (auto& c : s[i]) {
            pre = pre * bas + c;
            auto it = mp.find(pre);
            if (it == mp.end()) continue;

            for (auto& id : it->second) {
                if (id == i)    continue;
                ++pos[id];
                p[id] = p[id] * bas + s[id][pos[id]];
                mp[p[id]].push_back(id);
            }
            mp.erase(it);
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << endl;
    }

    return 1;
}

F、Train Wreck

题目大意

给你一个长度为的出栈入栈序列，你现在有辆列车，第辆列车颜色为，你要让每次停留在栈中颜色排列是唯一的。问是否可行，如果可行输出进栈颜色方案。

Solution

考点：堆

我们可以把出栈入栈转换成一棵树来考虑，初始栈为空的时候假设我们有一个节点的树并且这个结点编号为，接下来入栈就是当前节点新开辟一个儿子，出栈就是回到父亲，一直这样操作一个合理的出栈入栈顺序就会生成个节点。我们要做的就是给生成的个节点打上颜色，让每个点到的路径上构成的颜色序列唯一。

那么就很明显，我们每次让任意一个节点它的儿子节点们颜色互不相同就可以了。

我们用的方式填颜色，把同层次的颜色先选上不一样种颜色，并且每种颜色减一后插回原来的序列中。

我们使用堆可以很好的维护上面的数据结构。

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define debug(x) cout << #x << ":" << x << '\n'
typedef tuple<int, int> tup;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = 2e6 + 7;
ll n, m;
int p[N];
char s[N];

// (()()()()()())


multiset<pai, greater<pai>> st;
vector<int> len[N];

int a[N];

int solve() {
    n = read();
    scanf("%s", s + 1);
    unordered_map<int, int> cnt;
    for (int i = 1; i <= n; ++i)    p[i] = read(), ++cnt[p[i]];

    for (int i = 1; i <= n; ++i) {
        if (cnt.count(i)) {
            st.insert({ cnt[i],i });
        }
    }

    int now = 0;
    for (int i = 1; i <= 2 * n; ++i) {
        if (s[i] == '(') {
            ++now;
            len[now].push_back(i);
        }
        else --now;
    }

    for (int i = 1; i <= n; ++i) {
        int sz = len[i].size();
        if (sz) {
            multiset<pai, greater<pai>> tmp;
            for (int j = 1; j <= sz; ++j) {
                if (st.empty()) {
                    puts("NO");
                    exit(0);
                }
                auto it = *st.begin();
                if (it.first == 0) {
                    puts("NO");
                    exit(0);
                }
                st.erase(st.find(it));
                tmp.insert(it);
            }
            for (auto& pos : len[i]) {
                auto it = *tmp.begin();
                a[pos] = it.second;
                tmp.erase(tmp.find(it));
                st.insert({ it.first - 1, it.second });
            }
        }
    }


    return 1;
}

signed main() {
    //int T = read(); for (int i = 1; i <= T; ++i)
    {
        //solve();
        cout << (solve() ? "YES" : "NO") << endl;
        stack<int> stk;
        for (int i = 1; i <= 2 * n; ++i) {
            if (s[i] == '(')    print(a[i], 32);
        }
        puts("");
    }
    return 0;
}

G、Game of Death

题目大意

场上共有个人，现在每个人都会随机选择一个其他人开枪，并且成功命中其他人的概率为。

你需要输出场上留下个人的概率，分式对取模。

Solution

考点：子集反演+NTT

首先考虑状态设计，我们让代表被击中的是集合的概率，我们让代表被击中的是子集的概率。

所以我们可以得出。

接下来根据子集反演的公式，我们可以得出。

我们就把问题转变成求击中概率是子集的概率了，这个是比较好求的，如果我们假设代表开枪没打中人的概率。

集合中的人只能开枪没打中或者打中了中除自己以外的某个人，由于每个人都是独立的，概率直接做乘法即可；对于集合外的人，他们只能开枪没打中或者打中了集合中的某个人，同样做出乘法就可以算到。

然后又可以发现和只和集合大小有关和具体选择了那个集合没有关系。

所以我们假设是被击中集合大小为的所有概率之和，那么他就是行的答案。

然后后面那个求和又可以转换成卷积的形式快速求解到，我们把看成，那么后面这个式子就变成了定值的多项式，直接让，把就可以求解到后面的答案了。

const int N = 3e5 + 7; // 2^21

int n, a, b, p, q;
int jc[N], inv[N], G[N];

namespace NTT {
    int limit;
    vector<int> A, B, rev;
    inline int add(int x, int y) { return x += y, x >= MOD ? x - MOD : x; }
    inline int mul(int x, int y) { return 1ll * x * y % MOD; }
    int qpow(int x, int y) {
        int res = 1;
        for (; y; y >>= 1, x = mul(x, x)) if (y & 1) res = mul(res, x);
        return res;
    }
    void init() {
        int ed = n * 2, bit = -1;
        for (limit = 1; limit <= ed; limit <<= 1) ++bit;
        A.resize(limit); B.resize(limit); rev.resize(limit);
        for (int i = 0; i < limit; ++i)    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bit);
    }
    void ntt(vector<int>& P, int op) {
        for (int i = 0; i < limit; ++i) {
            if (i < rev[i])swap(P[i], P[rev[i]]);
        }
        for (int mid = 1; mid < limit; mid <<= 1) {
            int euler = qpow(3, (MOD - 1) / (mid << 1));
            if (op < 0)    euler = qpow(euler, MOD - 2);
            for (int i = 0, pos = mid << 1; i < limit; i += pos) {
                int wk = 1;
                for (int j = 0; j < mid; ++j, wk = mul(wk, euler)) {
                    int x = P[i + j], y = mul(wk, P[i + j + mid]);
                    P[i + j] = add(x, y), P[i + j + mid] = add(x, MOD - y);
                }
            }
        }
        if (op > 0)    return;
        int inv = qpow(limit, MOD - 2);
        for (int i = 0; i < limit; ++i)    P[i] = mul(P[i], inv);
    }
    void work() {
        for (int i = 0; i <= n; ++i) A[i] = i & 1 ? MOD - inv[i] : inv[i];
        for (int i = 0; i <= n; ++i) B[i] = mul(G[i], inv[i]);
        ntt(A, 1), ntt(B, 1);
        for (int i = 0; i < limit; ++i)    A[i] = mul(A[i], B[i]);
        ntt(A, -1);
    }
}using namespace NTT;


void init(int n) {
    jc[0] = 1;
    for (int i = 1; i <= n; ++i) {
        jc[i] = mul(jc[i - 1], i);
    }
    inv[n] = qpow(jc[n], MOD - 2);
    for (int i = n - 1; i >= 0; --i) {
        inv[i] = mul(inv[i + 1], i + 1);
    }
}
int C(int n, int m) {
    return 1ll * jc[n] * inv[n - m] % MOD * inv[m] % MOD;
}

int solve() {
    n = read(), a = read(), b = read();

    init(n);
    p = mul(a, qpow(b, MOD - 2)); // 没打中概率
    q = (1 - p + MOD) % MOD; // 打中概率

    int tmp_inv = mul(inv[n - 1], jc[n - 2]);
    for (int i = 0; i <= n; ++i) {
        G[i] = mul(qpow(add(q, mul(mul(p, i - 1), tmp_inv)), i), qpow(add(q, mul(mul(p, i), tmp_inv)), n - i));
    }
    init(), work();
    for (int i = n; i >= 0; --i) {
        print(1ll * C(n, i) * A[i] % MOD * jc[i] % MOD);
    }

    return 1;
}

H、War of Inazuma (Easy Version)

题目大意

你要构造一个长度为的字符串，一个下标在和其他下标的二进制表示只有一个不相同的有一条边，和这个点直接相连的下标和同一种字符最多出现次数为。

Solution

方法1.队列实现

我们让字符串最后一个为，它对应的下标就是一个二进制全为的，接下来和它相连的就是有一位为的二进制表示，把这些全部标成。这样一层一层往下用队列防止多次标记，用去依次把某些位置变成相反的值。

ll n, m;
int p[N];
bool vis[N];

inline int lowbit(int x) { return x & (-x); }

int solve() {
    n = read();
    m = (1 << n) - 1;
    queue<int> pq;

    pq.push(m);
    p[m] = 1;

    while (pq.size()) {
        int now = pq.front();
        pq.pop();
        if (vis[now])   continue;
        vis[now] = 1;
        for (int x = now, y; x; x -= y) {
            y = lowbit(x);
            p[now ^ y] = !p[now];
            pq.push(now ^ y);
        }
    }
    for (int i = 0; i <= m; ++i) {
        printf("%d", p[i]);
    }

    return 1;
}

方法2.内置函数

我们把上面那种方法展开画图可以发现，二进制表示有个的在一层，有个的在一层，有个的在一层，所以我们直接按每个数二进制里面有多少个分类就行。

int solve() {
    n = read();
    m = (1 << n) - 1;

    for (int i = 0; i <= m; ++i) {
        putchar('0'+(__builtin_popcount(i) & 1));
    }

    return 1;
}

多校补题暂时告一段落了，度过了一个充实的暑假