模拟赛 - NOI 模拟一

2015.12.05 18:20 Sat| 10 visits oi_2016| 2016_竞赛日常| Text

NOI 模拟一

pengzhou 命题,真是开心。第一题是一道没有人 AC 的字符串,第二题是一道有人骗过的 DP,第三题是一道卡常的 FFT。

密码破译

给出一个长度小于 8000 的字符串,按顺序输出它编号为 q 的倍数的子串的最后一位。

在求出后缀数组之后,一层一层递归找子串,时间复杂度 O(N^2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

#define N 20000

char str[N], *s[N];
int n, q, sa[N], x[N], y[N], c[N];

inline bool same(int a, int b, int l)
{
    return y[a] == y[b] &&
                ((a + l >= n && b + l >= n) ||
                (a + l < n && b + l < n && y[a + l] == y[b + l]));
}

void get_sa(int m = 256)
{
    for (int i = 0; i < n; ++i)         ++c[x[i] = str[i]];
    for (int i = 1; i < m; ++i)         c[i] += c[i - 1];
    for (int i = n - 1; i >= 0; --i)    sa[--c[x[i]]] = i;
    for (int k = 1; k < n; k <<= 1)
    {
        int p = 0;
        for (int i = n - k; i < n; ++i)     y[p++] = i;
        for (int i = 0; i < n; ++i)         if (sa[i] >= k) y[p++] = sa[i] - k;
        memset(c, 0, m * sizeof(int));
        for (int i = 0; i < n; ++i)         ++c[x[y[i]]];
        for (int i = 1; i < m; ++i)         c[i] += c[i - 1];
        for (int i = n - 1; i >= 0; --i)    sa[--c[x[y[i]]]] = y[i];
        for (int i = 0; i < n; ++i)         y[i] = x[i];
        m = 0; x[sa[0]] = 0;
        for (int i = 1; i < n; ++i)
            x[sa[i]] = same(sa[i], sa[i - 1], k) ? m : ++m;
        if (++m == n) break;
    }
}

void print(char c)
{
    static int tot = 0;
    if ((++tot) % q == 0) putchar(c);
}

void getans(int l, int r, int len)
{
    if (s[l][len]) print(s[l][len]);
    int last = l;
    for (int i = l + 1; i <= r; ++i)
    {
        if (!s[i][len]) continue;
        if (s[i][len] != s[i - 1][len])
            if (s[i - 1][len])
                getans(last, i - 1, len + 1), last = i;
        print(s[i][len]);
    }
    if (s[r][len]) getans(last, r, len + 1);
}

int main()
{
    freopen("decrypt.in", "r", stdin);
    freopen("decrypt.out", "w", stdout);
    cin >> n >> q;
    scanf("%s", str);
    get_sa();
    for (int i = 0; i < n; ++i)
        s[i] = &str[sa[i]];
    getans(0, n - 1, 0);
    puts("");
    return 0;
}

圣诞树

原题:CF 140E。

设 T(i, j) 表示恰好用 j 种颜色布置长为 i 的一行的方案数。有 DP 方程 T(i, j) = T(i - 1, j) * (j - 1) + T(i - 1, j - 1),后面的两项分别表示最后一位是之前出现过的颜色还是新的颜色。考场上这里没想出来,只得了 40 分。

然后求总方案数是比较方便的,设 F(i, j) 表示第 i 行用 j 种颜色布置的方案数,那么 F(i, j) = (∑F(i - 1) * C(m, j) - F(i - 1, j)) * T(l(i), j)。然而这里需要求一个组合数,其中下标是确定的 m < 1e6,上标是从 1 到 5000 的所有数。

比较令人纠结的一点是取模的数不是素数。这里万峰源用了 【礼物】的解法,然而由于我比较弱,就直接把分数线上面的数存了起来,每一次除法的时候约分……于是在 CF 上万峰源 TLE 了,我 AC 了。

然后需要注意的是 F 数组需要滚动,每一次清空的时候很容易出错。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define N 1000005
#define L 5005

int n, m, p, maxt, l[N], temp[L];
long long t[L][L], sum[N], c[L], f[2][L];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}

void get_c(int m, int l)
{
    for (int i = 1; i <= l; ++i)
    {
        temp[i] = m - i + 1;
        for (int now = i, j = 1; now != 1; ++j)
        {
            int g = gcd(now, temp[j]);
            temp[j] /= g; now /= g;
        }
        c[i] = 1;
        for (int j = 1; j <= i; ++j)
            c[i] = c[i] * temp[j] % p;
    }
}

int main()
{
    freopen("christmas.in", "r", stdin);
    freopen("christmas.out", "w", stdout);
    cin >> n >> m >> p;
    for (int i = 1; i <= n; ++i)
        l[i] = read(), maxt = max(maxt, l[i]);
    get_c(m, min(m, maxt));
    t[0][0] = 1;
    for (int j = 1; j <= min(m, maxt); ++j)
    {
        t[j][j] = t[j - 1][j - 1] * j % p;
        for (int i = j + 1; i <= maxt; ++i)
            t[i][j] = (t[i - 1][j] * (j - 1) % p + t[i - 1][j - 1] * j % p) % p;
    }
    sum[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= l[i] && j <= m; ++j)
            f[1][j] = ((sum[i - 1] * c[j] - f[0][j]) % p * t[l[i]][j] % p + p) % p,
            sum[i] += f[1][j];
        for (int j = min(l[i], m) + 1; j <= l[i - 1] && j <= m; ++j)
            f[0][j] = f[1][j] = 0;
        memcpy(f[0], f[1], sizeof(long long) * (min(m, l[i]) + 1));
        memset(f[1], 0, sizeof(long long) * (min(m, l[i]) + 1));
        sum[i] %= p;
    }
    cout << sum[n] << endl;
    return 0;
}

BZOJ3645 Maze

递推方程很显然,卷积也很显然,倍增也很显然。

于是我在考场上想了出来并在本机 AC 了此题,在老师那里被卡了一点常数,差评!大概手写一个 complex 就好了。

不开 O2 本机上后五个点大约 3s,标程 2s。开 O2 后 0.2s。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>
using namespace std;

#define N 33000

long long n;
int m, k, a[N], b[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct comp
{
    double x, y;
    comp(double _x = 0.0, double _y = 0.0) : x(_x), y(_y) {}
    comp operator +(comp &c) { return comp(x + c.x, y + c.y); }
    comp operator -(comp &c) { return comp(x - c.x, y - c.y); }
    comp operator *(comp &c) { return comp(x * c.x - y * c.y, x * c.y + y * c.x); }
    double real() { return x; }
    double imag() { return y; }
};

comp ca[N], cb[N];
const double pi = 3.14159265358979323;

void fft(comp x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        comp wn(cos(type * 2 * pi / s), sin(type * 2 * pi / s));
        for (int i = 0; i < n; i += s)
        {
            comp w(1, 0), t;
            for (int j = 0; j < s >> 1; w = w * wn, ++j)
            {
                t = w * x[i + j + (s >> 1)],
                x[i + j + (s >> 1)] = x[i + j] - t, x[i + j] = x[i + j] + t;
            }
        }
    }
}

void multi(int a[], int b[], int tag = 0)
{
    int t = 2;
    for (int i = m; i; i >>= 1) t <<= 1;
    if (!tag)
    {
        for (int i = 0; i < m; ++i) ca[i] = a[i];
        for (int i = m; i < t; ++i) ca[i] = 0;
        fft(ca, t, 1);
        for (int i = 0; i < m; ++i) cb[i] = b[i];
        for (int i = m; i < t; ++i) cb[i] = 0;
        fft(cb, t, 1);
        for (int i = 0; i < t; ++i) ca[i] = ca[i] * cb[i];
    }
    else
    {
        if (tag == 2)
        {
            for (int i = 0; i < m; ++i) cb[i] = b[i];
            for (int i = m; i < t; ++i) cb[i] = 0;
            fft(cb, t, 1);
        }
        for (int i = 0; i < t; ++i) ca[i] = cb[i] * cb[i];
    }
    fft(ca, t, -1);
    for (int i = 0; i < m; ++i)
        a[i] = int(ca[i].real() / t + 0.1) % 19;
}

void power(long long n)
{
    while (n)
    {
        if (n & 1) multi(a, b), multi(b, b, 1);
        else multi(b, b, 2); n >>= 1;
    }
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) a[i] = read();
    for (int i = 0; i < k; ++i) b[i] = read();
    power(n - 1);
    for (int i = 0; i < m; ++i)
        printf("%d ", a[i]);
    return 0;
}