一些有趣的问题合集

这些问题大多数出自于做过的模拟题，大多数在OJ上都找不到。

因为大部分模拟题不再被允许发博客，所以这个合集停更了。

从这里开始

1. kand
2. 青蛙
3. dalao
4. 区间
5. Lasting Moment
6. FLOJ Round

kand

Problem Descript

　　给定$n$个数，从中选出$k$个数，问使得它们and和为$s$的方案数。

Input

　　第一行三个正整数$n$, $k$和$s$。

　　接下来有$n$行，每行一个整数$a_{i}$表示第$i$个数。

Output

　　仅一行，一个整数，表示答案对$10^{9} + 7$取模后的结果。

Sample

input

3 2 2
3
2
1

output

1

Limit

对于10%的数据满足$1\leqslant n \leqslant 10, 0 \leqslant a_{i}, s \leqslant 2^{10}$
对于30%的数据满足$1\leqslant n \leqslant 100, 0 \leqslant a_{i}, s \leqslant 2^{10}$
对于70%的数据满足$1\leqslant n \leqslant 10^{5}, 0 \leqslant a_{i}, s \leqslant 2^{15}$
对于所有的数据满足$1\leqslant n \leqslant 10^{5}, 0 \leqslant a_{i}, s \leqslant 2^{20}$

Source

idy002 

Solution 1

　　暴力枚举$k$组合。期望得分10分。

Solution 2

　　用$f[i][j][k]$表示考虑到前$i$个数中，选出$j$个数，它们的and和为$k$的方案数。

　　时间复杂度$O(n^{2}2^{W})$，期望得分30分。　　

Solution 3

　　当首先过滤掉$s\  and\  a_{i} \neq s$的数。

　　当$s$的某一位为0时，那么选出的数至少有一个这一位为0，那么可以考虑容斥。

　　用所有方案减去存在不合法的方案。

　　不合法的方案可以枚举每次选出来的数哪几位为1，然后暴力计算$cnt$，用组合数算方案。

　　时间复杂度$O(3^{W} + n)$，期望得分70分。

Solution 4

　　发现暴力求$cnt$的过程是FWT的正变换。

　　于是FWT优化一下就好了。

　　时间复杂度$O(W\cdot 2^{W} + n)$，期望得分100分。

Code

#include <iostream>
#include <cstdio>
using namespace std;
typedef bool boolean;

const int Val = (1 << 20), mask = Val - 1, M = 1e9 + 7;

void exgcd(int a, int b, int& d, int& x, int& y) {
    if (!b)
        d = a, x = 1, y = 0;
    else {
        exgcd(b, a % b, d, y, x);
        y -= (a / b) * x;
    }
}

int inv(int a, int n) {
    int d, x, y;
    exgcd(a, n, d, x, y);
    return (x < 0) ? (x + n) : (x); 
}

int n, k, s;
int *jc, *ijc;
int cnt[Val];

inline void init() {
    scanf("%d%d%d", &n, &k, &s);
    jc = new int[(n + 1)];
    ijc = new int[(n + 1)];
    int nc = 0, S = s ^ mask;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        if ((s & x) == s)
            cnt[x & S]++, nc++;
    }
    n = nc;
}

inline void prepare() {
    jc[0] = 1;
    for (int i = 1; i <= n; i++)
        jc[i] = jc[i - 1] * 1ll * i % M;
    ijc[n] = inv(jc[n], M);
    for (int i = n - 1; ~i; i--)
        ijc[i] = ijc[i + 1] * 1ll * (i + 1) % M; 
}

inline int C(int n, int k) {
    if (n < k)    return 0;
    return (jc[n] * 1ll * ijc[k]) % M * ijc[n - k] % M;
}

inline void solve() {
    int ans = C(n, k), S;
    for (int i = 0; i < 20; i++) {
        S = mask ^ (1 << i);
        for (int j = S; j; j = (j - 1) & S)
            cnt[j] += cnt[j | (1 << i)];
    }
    S = s ^ mask; 
    for (int i = S, sign, j; i; i = (i - 1) & S) {
        if (cnt[i]) {
            for (j = i, sign = 1; j; j -= j & (-j), sign *= -1);
            ans = (ans + sign * C(cnt[i], k)) % M;
            if (ans < 0)    ans += M;
        }
    }
    printf("%d\n", ans);
}

int main() {
    freopen("kand.in", "r", stdin);
    freopen("kand.out", "w", stdout); 
    init();
    prepare();
    solve();
    return 0;
}

kand

青蛙

Solution 1

　　直接暴力枚举所有情况。

　　时间复杂度$O(2^{m})$。期望得分20分。

Solution 2

　　设当前考虑第$i$只青蛙跳跃。

　　那么这次后，它结束的位置的期望是$x_{i}' = \frac{x_{i} - 2(x_{i} - x_{i - 1}) + x_{i} - 2(x_{i} - x_{i + 1})}{2}=x_{i + 1} + x_{i - 1} - x_{i}$。

　　然后暴力递推。时间复杂度$O(mk)$。期望得分40分。

Solution 3

　　暴力打表可以发现在$n, m \geqslant 10^{3}$时，随即数据下，操作的循环节大约在$5000$左右。

　　然后找一下循环节，就可以骗到70分。

Solution 4

　　可以发现一个有趣的事情：

$x_{i}' - x_{i - 1}= x_{i + 1} - x_{i}$
$x_{i + 1} - x_{i}' = x_{i} - x_{i - 1}$

　　这相当于一次操作交换了相邻的两个差。

　　这个可以看成一个置换。可以处理出一轮操作的置换，最终的差分数组等于先把这个置换进行$k$次幂，然后作用在原来的差分数组上。

　　由于置换的合成是$O(n)$的，所以可以直接快速幂，时间复杂度$O(n\log k)$

　　也可以把置换看成轮换，把中间每个环拉出来，然后往前走$k$步，时间复杂度$O(n)$。

　　期望得分100分。

　　由于我比较懒，就只给出快速幂的代码。

Code

#include <iostream>
#include <cstring>
#include <cstdio>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;

#define ll long long

const int N = 1e5 + 5;

typedef class MyVector {
    public:
        int a[N];

        MyVector() { }
        MyVector(int n) {
            for (int i = 1; i <= n; i++)
                a[i] = i;
        }
        MyVector(int* ar, int n) {
            for (int i = 1; i <= n; i++)
                a[ar[i]] = i;
        }

        int& operator [] (int p) {
            return a[p];
        }
}MyVector;

int n, m;
ll k;
int *ar, *qr;
int *da, *nda;

MyVector operator * (MyVector a, MyVector b) {
    MyVector rt;
    for (int i = 1; i < n; i++)
        rt[i] = a[b[i]];
    return rt;
}

MyVector qpow(MyVector& a, ll pos) {
    MyVector pa = a, rt(n - 1);
    for ( ; pos; pos >>= 1, pa = pa * pa)
        if (pos & 1)
            rt = pa * rt;
    return rt;
}

inline void init() {
    scanf("%d", &n);
    ar = new int[(n + 1)];
    qr = new int[(n + 1)];
    da = new int[(n + 1)];
    nda = new int[(n + 1)];
    for (int i = 1; i < n; i++)
        qr[i] = i;
    for (int i = 1; i <= n; i++)
        scanf("%d", ar + i);
    for (int i = 1; i < n; i++)
        da[i] = ar[i + 1] - ar[i];
    scanf("%d"Auto, &m, &k);
    for (int i = 1, x; i <= m; i++) {
        scanf("%d", &x);
        swap(qr[x - 1], qr[x]);
    }
}

MyVector a;

inline void solve() {
    a = MyVector(qr, n - 1);
    a = qpow(a, k);
    for (int i = 1; i < n; i++)
        nda[a[i]] = da[i];
    ll ps = ar[1];
    printf(Auto"\n", ps);
    for (int i = 1; i < n; i++) {
        ps += nda[i];
        printf(Auto"\n", ps);
    }
}

int main() {
    freopen("frog.in", "r", stdin);
    freopen("frog.out", "w", stdout);
    init();
    solve();
    return 0;
}

青蛙

dalao

　　注：因为样例2有错所以被我删掉了。

Solution 1

　　暴力枚举每一对$(x, y)$

　　时间复杂度$O(n^{2})$，期望得分10分。

Solution 2

　　经典的三维偏序问题。

　　可以CDQ分治或者树套树。

　　时间复杂度$O(n \log ^{2} n)$，期望得分60 ~ 100分。（某ZJC加上各种毒瘤优化，卡进时限4s，实际上时间限制可以只开2s）。

Solution 3

　　设$K_{x, y} = [a_{x} < a_{y}] + [b_{x} < b_{y}] + [c_{x} < c_{y}]$

　　$S_{x, y} = \max \{K_{x, y}, K_{y, x}\}$。

　　显然$S_{x, y} \in \{2, 3\}$。

　　设$A = \sum_{1\leqslant x < y \leqslant n}[S_{x, y} = 3]$, $B =  \sum_{1\leqslant x < y \leqslant n}[S_{x, y} = 2]$。

　　那么$A$就是问题所要我们求的。　　

　　另外，设$P_{a, b} = \sum_{1 \leqslant x, y \leqslant n}[a_{x} < a_{y}][b_{x} < b_{y}]$。

　　有注意到$A + B = C_{n}^{2}$。然后细心会发现：

　　$3\times A + B =P_{a, b} + P_{a, c} + P_{b, c}$

　　因为每一对合法的无序对$(x, y)$都会对右边的式子作出3次贡献，不合法的无序对会对右边的式子作出1次贡献。

　　然后根据这两个式子解解方程就能得到$A$了。

　　时间复杂度$O(n \log n)$，期望得分100分。

Code

#include <iostream>
#include <cstdlib> 
#include <cstring>
#include <cstdio>
#include <ctime>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif 
using namespace std;
typedef bool boolean;

#define ll long long

typedef class IndexedTree {
    public:
        int s;
        int* ar;
        
        IndexedTree() {        }
        IndexedTree(int n):s(n) {
            ar = new int[(n + 1)];
            memset(ar, 0, sizeof(int) * (n + 1));
        }
        
        void add(int idx, int x) {
            for ( ; idx <= s; idx += (idx & (-idx)))
                ar[idx] += x;
        }
        
        int getSum(int idx) {
            int rt = 0;
            for ( ; idx; idx -= (idx & (-idx)))
                rt += ar[idx];
            return rt;
        }
}IndexedTree;

int myrand(int& seed) {
    return seed = ((seed * 19260817ll) ^ 233333) & ((1 << 24) - 1);
}

void gen(int* ar, int s, int n) {
    for (int i = 1; i <= n; i++)    ar[i] = i;
    for (int i = 1; i <= n; i++)    swap(ar[i], ar[myrand(s) % i + 1]);
}

int n;
ll res = 0;
int *ar, *br, *cr;
int *ls;
IndexedTree it;

inline void init() {
    scanf("%d", &n);
    int sa, sb, sc;
    scanf("%d%d%d", &sa, &sb, &sc);
    ar = new int[(n + 1)];
    br = new int[(n + 1)];
    cr = new int[(n + 1)];
    ls = new int[(n + 1)];
    it = IndexedTree(n);
    gen(ar, sa, n);
    gen(br, sb, n);
    gen(cr, sc, n);
}

ll calc(int* ar, int* br) {
    for (int i = 1; i <= n; i++)
        ls[ar[i]] = br[i];
    ll rt = 0;
    memset(it.ar, 0, sizeof(int) * (n + 1));
    for (int i = 1; i <= n; i++) {
        rt += it.getSum(ls[i]);
        it.add(ls[i], 1);
    }
    return rt;
}

inline void solve() {    
    res = calc(ar, br);
    res += calc(ar, cr);
    res += calc(br, cr);
    res -= n * 1ll * (n - 1) / 2;
    res /= 2;
    printf(Auto, res);
}

int main() {
    freopen("dalao.in", "r", stdin);
    freopen("dalao.out", "w", stdout);
    init();
    solve();
    return 0;
}

dalao

区间

Solution 1

　　找出所有连续区间。然后用dp的思想去更新答案就好了。

　　时间复杂度$O(n^{2} + m)$，期望得分30分、

Solution 2

　　由于是一个排列，所以式子可以写成$max - min = r - l$。考虑暴力找连续区间的过程是枚举$l$，然后再枚举$r$的过程。当$l$不变的时候，$r$递增，如果$max$和$min$均为改变有一点小浪费。

　　因此可以考虑将$max$和$min$分段，然后每段每段地跳，每跳一次段可以直接计算出位置，然后判断一下是否合法。

　　时间复杂度$O(n^{2} + m)$，期望得分30 ~ 70分、

Solution 3

　　注意到两个连续区间如果存在公共部分，那么将它们合并后也一定是一个连续区间。

　　因为这是一个排列，所以将公共部分去掉后的两个区间的值域不会相交。不难证明两个连续区间合并的值域长度等于新区间的长度。

　　因此可以考虑CDQ分治。假设当前分治区间$[l, r]$，分治中心$mid$。

　　我可以枚举一个$l'$然后找到一个最短的包含区间$[l', mid + 1]$的区间。

　　这个可以用一个st表存值的大小，一个st表存一个值对应的下标。

　　当要求包含区间$[l, r]$的时候，可以在第一个st表中查询这一段的最大值和最小值，然后在第二个st表中查询这一段值域中的每个值在原数组中出现的下标的最大值r'和最小值l'。也就是意味着要包含区间$[l', r']$，于是便可以这样迭代去查。终止条件是$l' = l, r' = r$。

　　不理解st表维护的信息？那么换个解释方法，前者对数组$a_{i}$的区间最大最小值建立st表，后者对数组$b_{a_{i}} = i$的区间最大最小值建立st表。

　　但是这样做时间复杂度有问题，不可能每个位置都去查找一次。

　　可以继续发现一些优美性质：

性质1 如果存在四个整数满足$1 \leqslant l' < l \leqslant r' < r \leqslant n$，且使得$[l', r'],[l, r]$是连续的，那么$[l', r]$也是连续的。

　　证明 因为这是一个排列，所以非公共部分的值域是没有交集的。因此公共部分的值域是连续的。所以$[l', r]$也是连续的。

性质2 分治时，当要找到包含区间$[l', mid + 1]$时，且长度尽量小，可选的区间是唯一的。

　　证明 假设存在两个候选区间$[a, b],[c,d]$且满足$b - a = d - c, l\leqslant a < c \leqslant l' < mid + 1 \leqslant b < d \leqslant r$。

　　那么根据性质1，可以找到区间$[c, b]$作为答案。显然$b - c < d - c$，与候选区间要求满足的性质矛盾。

　　也许有些人会有点怀疑这个迭代做法的正确性，这个过程中，暂时先不考虑时间复杂度的问题。

算法的正确性 如果枚举左端点$l'$，那么找到的合法区间$[a, b]$是长度最小的。

　　证明  合法性 根据迭代终止条件和迭代过程易证（一个是要求连续，一个是要求包含$[l', mid + 1]$）。

　　最优性 假设存在一个更优的区间$[c, d]$，根据性质2，我们有$a < c, d \leqslant b$或$a \leqslant c, d < b$，因为要求包含$[l', mid + 1]$，而迭代是先从这个区间开始的，所以必然存在一个区间$[e, f]$恰好被$[c, d]$包含并且迭代的下一个区间没有被$[c, d]$包含（PS：如果下一个区间恰好为$[c, d]$，易证它不合法）。因此$[e, f]$的最小值和最大值之间每一个数都要在$[c, d]$中出现，但是根据迭代过程可知，必然存在一个$x$，使得它存在于$[e, f]$的最小值和最大值之间，但不在$[c, d]$中，因此$[c, d]$不是一个连续区间，与题目要求矛盾。

　　所以综上所述，算法是正确的。

　　现在来考虑优化。

性质3 当枚举的左端点单调递减时，右端点不减。

　　证明 仍然考虑反证法。假设枚举存在两个最优区间$[a, b], [c, d]$，满足$l \leqslant a < c \leqslant b < d \leqslant r$。

　　根据性质1，$[c, b]$是一个更优的答案。因此$[c, d]$不是最优的区间，矛盾。

　　有了这种优美的性质，不难得到，每次找到的区间是真包含前一个区间。

　　所以对于上一个找到的区间$[a, b]$。我只要再将$a + 1$然后继续用迭代法去找下一个区间就行了。

　　对于右边我们仍然做一次类似的过程：枚举$r'$，找到包含区间$[mid, r']$的一些区间。

　　然后这有什么用呢？

　　这个过程找到了一系列左端点递减的跨过分治中心的合法区间和一系列右端点递增的跨过分治中心的合法区间。

　　对于查询一个区间$[l', r'], l \leqslant l' \leqslant r' \leqslant r$，我在左边找到一个左端点小于等于$l'$的区间，在右边找到一个右端点大于等于$r'$的区间。然后将这两个区间取并集（注意是取并集！）尝试去更新这个询问的答案。

　　这个方法很多，可以二分。由于值域很小，也可以直接求前后缀最值。

　　时间复杂度$O(n\log n + m\log n)$，期望得分100分。

Code

#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef bool boolean;

const int N = 1e5 + 5, bzmax = 18;

#define pii pair<int, int>
#define fi first
#define sc second

pii operator + (pii a, pii b) {
    return pii(min(a.fi, b.fi), max(a.sc, b.sc));
}

boolean operator < (pii a, pii b) {
    return a.sc - a.fi < b.sc - b.fi;
}

typedef class SparseTable {
    public:
        int log2[N];
        pii f[N][18];
        
        SparseTable() {    }
        SparseTable(int n, int *ar) {
            log2[1] = 0;
            for (int i = 2; i <= n; i++)
                log2[i] = log2[i >> 1] + 1;
            for (int i = 1; i < n; i++)
                f[i][0] = pii(ar[i], ar[i]) + pii(ar[i + 1], ar[i + 1]);
            for (int j = 1; j < bzmax; j++)
                for (int i = 1; i + (1 << j) <= n; i++)
                    f[i][j] = f[i][j - 1] + f[i + (1 << (j - 1))][j - 1];
        }
        
        pii query(int a, int b) {
            assert(a != b);
            int p = log2[b - a];
            return f[a][p] + f[b - (1 << p)][p];
        }
}SparseTable;

typedef class Query {
    public:
        int l, r;
        pii res;
}Query;

int n, m;
int *ar, *var;
Query *qs;
pii *ls, *rs;
SparseTable st1, st2;

inline void init() {
    scanf("%d", &n);
    ar = new int[(n + 1)];
    var = new int[(n + 1)];
    for (int i = 1; i <= n; i++)
        scanf("%d", ar + i);
    for (int i = 1; i <= n; i++)
        var[ar[i]] = i;
    scanf("%d", &m);
    qs = new Query[(n + 1)];
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &qs[i].l, &qs[i].r), qs[i].res = pii(1, n);
}

void dividing(int l, int r, vector<Query*>& qs) {
    if (qs.empty())    return;
    if (l == r) {
        for (int i = 0; i < (signed) qs.size(); i++)
            qs[i]->res = pii(l, l);
        return;
    }
    int mid = (l + r) >> 1;
    vector<Query*> ql, qr;
    for (int i = 0; i < (signed) qs.size(); i++)
        if (qs[i]->r <= mid)
            ql.push_back(qs[i]);
        else if (qs[i]->l > mid)
            qr.push_back(qs[i]);
    
    dividing(l, mid, ql);
    dividing(mid + 1, r, qr);

    int tl = 0, tr = 0;
    pii cur, nx, p1, p2;
    for (nx = cur = pii(mid, mid + 1); cur.fi >= l && cur.sc <= r; cur.fi--) {
        do {
            nx = st1.query(cur.fi, cur.sc);
            nx = st2.query(nx.fi, nx.sc);
        } while (cur != nx && (cur = nx).fi >= l && cur.sc <= r);
        if (cur.fi >= l && cur.sc <= r)
            ls[++tl] = cur;
    }

    for (nx = cur = pii(mid, mid + 1); cur.fi >= l && cur.sc <= r; cur.sc++) {
        do {
            nx = st1.query(cur.fi, cur.sc);
            nx = st2.query(nx.fi, nx.sc);
        } while (cur != nx && (cur = nx).fi >= l && cur.sc <= r);
        if (cur.fi >= l && cur.sc <= r)
            rs[++tr] = cur;
    }

    int l1, l2, r1, r2;
    Query *q;
    for (int i = 0; i < (signed) qs.size(); i++) {
        q = qs[i];
        if (q->l < ls[tl].fi || q->r > rs[tr].sc)    continue;
        l1 = 1, r1 = tl, l2 = 1, r2 = tr;
        while (l1 <= r1) {
            mid = (l1 + r1) >> 1;
            if (ls[mid].fi <= q->l)
                r1 = mid - 1;
            else
                l1 = mid + 1;
        }

        while (l2 <= r2) {
            mid = (l2 + r2) >> 1;
            if (rs[mid].sc >= q->r)
                r2 = mid - 1;
            else
                l2 = mid + 1;
        }
        cur = (ls[r1 + 1] + rs[r2 + 1]);
        if (cur < q->res)
            q->res = cur;
    }
    qs.clear();
}

vector<Query*> vs;
inline void solve() {
    ls = new pii[(n + 1)];
    rs = new pii[(n + 1)];
    for (int i = 1; i <= m; i++)
        vs.push_back(qs + i);
    st1 = SparseTable(n, ar);
    st2 = SparseTable(n, var);
    dividing(1, n, vs);
    for (int i = 1; i <= m; i++)
        printf("%d %d\n", qs[i].res.fi, qs[i].res.sc);
}

int main() {
    freopen("interval.in", "r", stdin);
    freopen("interval.out", "w", stdout);
    init();
    solve();
    return 0;
}

interval

Lasting Moment·改

*因为版权原因不得公示题面，只给出大意和数据范围。

 

Main idea

　　给定一个长串$S$，然后多次询问一个串$S'_{i}$，求$S$长度最短的子串使得$S'_{i}$至少在这个子串中出现了$K_{i}$次，输出它的长度。无解输出-1。

　　保证每次询问的串互不相同，总串长不超过$10^5$。

Limits

对于所有数据，$1\leqslant |S|, Q, \sum |S'_{i}|\leqslant 10^5$

• 子任务1：$1\leqslant |S|, Q, \sum |S'_{i}|\leqslant 10^3$，空间限制256M
• 子任务2：$1\leqslant |S|, Q, \sum |S'_{i}|\leqslant 10^4$，空间限制256M
• 子任务3：$1\leqslant |S|, Q, \sum |S'_{i}|\leqslant 10^5$，空间限制256M
• 子任务4：$1\leqslant |S|, Q, \sum |S'_{i}|\leqslant 10^5$，强制在线，空间限制16M

Solution 1

　　使用KMP暴力进行匹配，求出所有匹配位，然后利用相邻的$K$个更新答案。

　　时间复杂度$O(|S|Q + \sum |S|)$。

　　能够通过子任务1。

Solution 2

性质4 设$n = |S|$，所有匹配点的总个数不超过$2n\sqrt{\sum|S'_{i}|}$。

　　证明 考虑对于长度为$k$的所有询问串，最多可能产生的匹配点总个数为$n - k + 1$。

　　考虑最坏的情况下，询问一个长度为$k$的串，产生了$n - k + 1 \leqslant n$个匹配点。

　　这样至多可以询问$2\sqrt{\sum|S'_{i}|}$。因此得证。

　　然后考虑快速用数据结构找到所有匹配点。

　　比如后缀数组。我们可以在后缀数组中二分找到第一个以及最后一个把$S'_{i}$作为前缀的后缀。设$L = |S'_{i}|$，那么后缀数组中这一段的后缀都包含它作为前缀。

　　可以把这一段的sa暴力提取出来排序。然后做法同上。

　　时间复杂度$O(n\sqrt{\sum|S'_{i}|}\log n)$。可以通过子任务1和子任务2。

Solution 3

　　对询问串建立Trie树。暴力跳last，存下匹配点。最后暴力算答案。

　　时间复杂度$O(n\sqrt{\sum|S'_{i}|})$，可以通过子任务1和子任务2，3。

Solution 4

　　把解法2的排序改成基数排序，桶大小256或者512，可以通过所有数据（不含Extra Test）。　　

Code

#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
typedef bool boolean;
#define ll long long

const int N = 1e5 + 5, bzmax = 20;

typedef class Pair3 {
    public:
        int x, y, id;

        Pair3(int x = 0, int y = 0, int id = 0):x(x), y(y), id(id) {    }
}Pair3;

int n, q;
char str[N << 1];
int sa[N], rk[N], cnt[N];
Pair3 xs[N], ys[N];
char buf[N];

inline void init() {
    scanf("%s", str + 1);
    n = strlen(str + 1);
    scanf("%d", &q);
}

void radix_sort(Pair3* xs) {
    int m = max(n, 256);
    memset(cnt, 0, sizeof(int) * (m + 1));
    for (int i = 1; i <= n; i++)
        cnt[xs[i].y]++;
    for (int i = 1; i <= m; i++)
        cnt[i] += cnt[i - 1];
    for (int i = 1; i <= n; i++)
        ys[cnt[xs[i].y]--] = xs[i];

    memset(cnt, 0, sizeof(int) * (m + 1));
    for (int i = 1; i <= n; i++)
        cnt[ys[i].x]++;
    for (int i = 1; i <= m; i++)
        cnt[i] += cnt[i - 1];
    for (int i = n; i; i--)
        xs[cnt[ys[i].x]--] = ys[i];
}

void build_sa() {
    for (int i = 1; i <= n; i++)
        rk[i] = str[i];
    for (int k = 0, dif; k < bzmax; k++) {
        for (int i = 1; i + (1 << k) <= n; i++)
            xs[i] = Pair3(rk[i], rk[i + (1 << k)], i);
        for (int i = n - (1 << k) + 1; i <= n; i++)
            xs[i] = Pair3(rk[i], 0, i);
        radix_sort(xs);
        rk[xs[1].id] = dif = 1;
        for (int i = 2; i <= n; i++)
            rk[xs[i].id] = ((xs[i].x != xs[i - 1].x || xs[i].y != xs[i - 1].y) ? (++dif) : (dif));
        if (dif == n)
            break;
    }
    for (int i = 1; i <= n; i++)
        sa[rk[i]] = i;
}

int cnt1[512];
int ar[N], br[N];
void radix_sort(int* ar, int len) {
    const int temp = 511;
    boolean aflag = true;
    reverse(ar, ar + len);
    for (int i = 1; i < len; i++)
        if (ar[i] < ar[i - 1])
            aflag = false;
    if (aflag)
        return;
    int *x = ar, *y = br;
    for (int t = 0; t < 2; t++) {
        int bit = t * 9;
        memset(cnt1, 0, sizeof(cnt1));
        for (int i = 0; i < len; i++)
            cnt1[(x[i] >> bit) & temp]++;
        for (int i = 1; i <= temp; i++)
            cnt1[i] += cnt1[i - 1];
        for (int i = len - 1; ~i; i--)
            y[--cnt1[(x[i] >> bit) & temp]] = x[i];
        swap(x, y);
    }
    for (int i = 0; i < len; i++)
        ar[i] = x[i];
} 

inline void solve() {
    int K, len;
    while (q--) {
        scanf("%d%s", &K, buf + 1);
        len = strlen(buf + 1);
        
        int L = 1, R = n, l, r;
        for (int i = 1; i <= len && L <= R; i++) {
            l = L, r = R;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (str[sa[mid] + i - 1] >= buf[i])
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            L = r + 1;
            if (L > R)
                break;
            l = L, r = R;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (str[sa[mid] + i - 1] <= buf[i])
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            R = l - 1;
        }
        
        if (R - L + 1 < K)
            puts("-1");
//            continue;
        else {
            int res = 211985, lc = R - L + 1;
            for (int i = L; i <= R; i++)
                ar[i - L] = sa[i];
            radix_sort(ar, lc);
            for (int i = K - 1; i < lc; i++)
                res = min(ar[i] - ar[i - K + 1], res);
            printf("%d\n", res + len);
        }
    }
}

int main() {
    init();
    build_sa();
    solve();
    return 0;
}

Lasting Moment

FLOJ Round

　　（来自一道多校题）

Solution 1 

　　通过无穷项等比数列求和可以推出第一个选择是第一颗星星的概率。然后可以计算出期望得分。

　　期望得分10分。

Solution 2

　　暴力枚举排列计算概率。

　　期望得分40分。

Solution 3

　　用$f_{s, i}$表示剩下的星星的集合是$s$，当前走到第$i$个星星。然后概率动态规划，因为转移方程很简单，在环上代入消元解方程。

　　期望得分60分

Solution 4

　　考虑如何计算一个排列的字典序排名：

　　根据期望的线性，答案可以看成两部分相减：一部分是$a_{i} \times (n - i)!$，另一部分是以最终排列以$i$结尾的“正序对”的个数乘$(n - i)!$的期望。

　　设$dp_{n, i, j}$表示还剩下$n$个星星，考虑到倒数第$n$轮，第$i$个星星在倒数第$j$轮被删掉的概率。

　　转移的时候考虑当前的$1$是否被拿走。如果它没有被拿走就把环转动一圈，使$i$变为$i - 1$。

　　如果$1$被拿走，那么还剩下$n - 1$个星星，$i$变为$i - 1$。

　　因此当$n \neq j$的时候可以写成以下转移：（为了方便，假设$1 - 1 = n$）

$dp_{n, i, j} = \left (1 - \frac{p}{q} \right)dp_{n, i - 1, j} + \frac{p}{q}dp_{n - 1, i - 1, j}\times [i \neq 1]$

　　如果$n = j$，那么有：

$dp_{n, i, n} = \left (1 - \frac{p}{q} \right)dp_{n, i - 1, n} + \frac{p}{q}\times [i = 1]$

　　对于后一部分，由于每个位置被选与它上面的数无关，因此可以考虑设$dp_{n, i, d, j}$表示还剩$n$个星星，第$i$个星星在它后面的第$d$颗星星被拿走前的倒数第$j$轮被拿走的概率。转移类似于上面。

　　时间复杂度$O(n^4)$，期望得分80分。

Solution 5

　　注意到对于$dp_{n, i, *}$都有相似的转移，考虑设$f_{n, i} = \sum_{dp_{n, i, j}\times (j - 1)!}$，然后可以一起转移了。

　　对于第二个dp同理。于是时间复杂度成功降为$O(n^3)$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef bool boolean;

const int N = 305, M = 1e9 + 7;

void exgcd(int a, int b, int& x, int& y) {
    if (!b)
        x = 1, y = 0;
    else {
        exgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
}

int inv(int a, int n) {
    int x, y;
    exgcd(a, n, x, y);
    return (x < 0) ? (x + n) : (x);
}

int sub(int a, int b) {
    a -= b;
    if (a < 0)
        return a + M;
    return a;
}

int n, Pg, Pl;
int ar[N], jc[N];
int f[N][N], g[N][N][N];

inline void init() {
    scanf("%d%d%d", &n, &Pg, &Pl);
    Pg = Pg * 1ll * inv(Pl, M) % M, Pl = sub(1, Pg);
    for (int i = 1; i <= n; i++)
        scanf("%d", ar + i), ar[i]--;
    jc[0] = 1;
    for (int i = 1; i <= n; i++)
        jc[i] = jc[i - 1] * 1ll * i % M;
}

int res = 1;
inline void solve() {
    for (int rest = 1; rest <= n; rest++) {
        int a = 1, b = jc[rest - 1];
        for (int i = rest; i > 1; i--) {
            a = a * 1ll * Pl % M;
            b = (b + f[rest - 1][i - 1] * 1ll * a) % M;
        }
        b = b * 1ll * Pg % M;
        a = sub(1, a * 1ll * Pl % M);
        f[rest][1] = b * 1ll * inv(a, M) % M;
        for (int i = 2; i <= rest; i++)
            f[rest][i] = (Pl * 1ll * f[rest][i - 1] + Pg * 1ll * f[rest - 1][i - 1]) % M;
    }

    for (int i = 1; i <= n; i++)
        res = (res + ar[i] * 1ll * f[n][i]) % M;

    for (int rest = 1; rest <= n; rest++)
        for (int diff = 1; diff < rest; diff++) {
            // i is obtained after i + diff in reverse order.
            // And i is obtained at turn k.
            int a = 1, b = f[rest - 1][diff];
            for (int i = rest; i > 1; i--) {
                a = a * 1ll * Pl % M;
                if (i + diff != rest + 1)
                    b = (b + g[rest - 1][diff - (i + diff > rest)][i - 1] * 1ll * a) % M;
            }
            a = sub(1, a * 1ll * Pl % M);
            b = b * 1ll * Pg % M;
            g[rest][diff][1] = b * 1ll * inv(a, M) % M;
            for (int i = 2; i <= rest; i++) {
                g[rest][diff][i] = Pl * 1ll * g[rest][diff][i - 1] % M;
                if (i + diff != rest + 1)
                    g[rest][diff][i] = (g[rest][diff][i] + Pg * 1ll * g[rest - 1][diff - (i + diff > rest)][i - 1]) % M;
            }
        }

    for (int i = 1; i <= n; i++)
        for (int diff = 1; diff < n; diff++) {
            int j = i + diff;
            if (j > n)
                j -= n;
            if (ar[i] < ar[j])
                res = sub(res, g[n][diff][i]);
        }
    printf("%d", res);
}

int main() {
    init();
    solve();
    return 0;
}

FLOJ Round