绝渡逢舟模拟赛 Ⅱ

2016.01.15 20:36 Fri| 73 visits oi_2016| 2016_竞赛日常| Text

习用之语

题目描述

成语是古代汉语词汇中特有的一种长期相沿用的固定短语,来自于古代经典或著作、历史故事和人们的口头故事。成语的意思精辟,往往隐含于字面意义之中,不是其构成成分意义的简单相加。它结构紧密,一般不能任意变动词序,抽换或增减其中的成分。成语一共有 5 万多条,其中 96% 为四字格式。

成语具有结构固定性、意义整体性、语法功能的多样性的特点,很多成语都十分相似,如不孚众望、不负众望,瓮中捉鳖、瓮中之鳖,但是其意却失之毫厘谬以千里。也有许多成语仅两字、三字之差。

现有一本成语字典,出于兴趣,欲知其中仅差 D(1≤D≤4) 字的四字成语有多少对。

输入格式

第一行为两个正整数N、D,表示成语字典中共收录了N条四字成语,D如题中所描述。

接下来一行每行4个字符表示一个成语,所有字符均被编码为’0’-’9’或’a’-’z’表示。

输出格式

仅包含一个整数表示仅差D字的成语有多少对。

样例输入

4 2 
0000
a010
0202
a0e2

样例输出

3

数据范围和注释

对于15%的数据,N≤3000。

对于100%的数据,N≤50000。

八卦天盘

题目描述

所谓太极生两仪,两仪生四相,四相生八卦,八卦而变六十四,周而复始变化无穷。

传说八卦天盘决定世间万物的消长。八卦天盘中有若干阴阳球,阴阳球只能在天盘中规定的轨道内进行有向运动,盘中的轨道构成了一个N个结点 M条边的有向无环图。入度为零的K个位置各有一个阴阳球,同样的有K个出度为零终止位置。运动结束时,所有球都会停止在不同的终止位置,两个阴阳球不会经过相同的位置。我们将K个起始位置的球按照原来的编号大小叫做”球1,球2……”,终止位置同样按照编号大小叫做”终点 1,终点 2……”。若K个阴阳球所到达终点——一个1到K的排列,其中有偶数个逆序对,则时间万物将会增长一个单位,反之则万物消亡一个单位。

在一个轮回周期内,阴阳球将会周而复始的运动很多遍,对于每种合法的运动路径,阴阳球都会如此运动一次。现求解一个轮回周期万物将会增长多少(由于结果可能会很大,所以最终要将结果对一个素数P取模)。

输入格式

输入的第一行包含三个整数N,M,P如题中所述。

之后M行每行两个整数a,b表示有一条单向轨道从a点到b点。

输出格式

在一行内输出答案。

样例输入

4 2 1000003
1 3
2 4
4 2 1000003
4 1
3 2
4 4 1000003
2 1
2 4
3 1
3 4

样例输出

1
1000002
0

数据范围和注释

对于10%的数据,N≤10。

对于50%的数据,N≤300。

对于100%的数据,N≤600,M≤100000,2≤p≤10^9+7。

盈虚方田

题目描述

所谓方田者,田之正也。诸田不等,以方为正,故曰方田。

人们对一块矩形田地的审美感受主要取决于其长宽比例是否协调,确切的说与长和宽的最大公约数有:

当一个矩形长宽的最大公约数越“简单”时,人们看着它越舒服。一个数字的单纯度等于自身组成的质因子个数。例如

12=2*2*3,所以12的单纯度为3。特别的,1的单纯度为0。现在有若干个问题,在所有长不超过N,宽不超过M的整数边长的田地中,有多少种田地其长宽最大公约数的单纯度不超过P。

注记:求最大公约数之法,《九章算术》曾云:“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。” 此所谓更相减损之术也。

输入格式

第一行有一个整数T表示下面共有T组测试数据。

接下来每行三个整数N,M,P如题目中所描述意义相同。

输出格式

输出共T行每行一个整数表示题中所求不同田地的个数。

样例输入

2

10 10 0

10 10 1

样例输出

63

93

数据范围和注释

对于30%的数据N,M,P≤1000。

对于另外20%的数据T=1。 对于另外20%的数据P=0。

对于100%的数据 1≤N,M≤5*10^5,0≤P≤*10^5,T≤5000。

题解

习用之语

15%做法:暴力枚举两个串,O(4)检测。

100%做法:从0到15枚举每一位的状态,假设枚举到1011(11),就把每个串1,2,4位提出来,忽略第3位,统计处每种串有多少个。

如何得到答案呢?D=0时,每个串的答案就是和自己相同的串的个数,D=1时,考虑枚举哪三位是相同的,不考虑剩下的是否相同,然然后把对应位置和当前串相同的个数(前面统计过的)加上,然而我们发现我们多算了4位都相同的串,多算了几遍呢?4遍,所以减掉4遍和自己相同的串就行了。

D=2时,枚举哪两位相同,不考虑剩下的是否相同,然后把对应位置和当前串相同的个数(前面统计过的)加上,这次多算了3位相同和4为相同,3位算了3遍,4位算了6遍,减掉即可。

D=3,同理,2位相同算了2遍,3位3遍,4位4遍。

D=4,用n减去D=0,1,2,3时的情况就好了。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 50005
#define calc(c) (isdigit(c) ? c - '0' + 1 : c - 'a' + 11)

int n, d;
long long f[16], ans[5];
char str[N][4];
int mp[2000005];

int main()
{
    freopen("idioms.in", "r", stdin);
    freopen("idioms.out", "w", stdout);
    cin >> n >> d;
    for (int i = 1; i <= n; ++i)
        scanf("%s", str[i]);
    for (int i = 0; i <= 15; ++i)
    {
        memset(mp, 0, sizeof mp);
        for (int j = 1; j <= n; ++j)
        {
            int t = 0;
            for (int k = 0; k < 4; ++k)
                if (i >> k & 1) t = t * 37 + calc(str[j][k]);
                else t *= 37;
            f[i] += mp[t], mp[t] += 1;
        }
    }
    ans[0] = f[15];
    ans[1] = f[7] + f[11] + f[13] + f[14] - 4 * ans[0];
    ans[2] = f[3] + f[5] + f[6] + f[9] + f[10] + f[12] - ans[1] * 3 - ans[0] * 6;
    ans[3] = f[1] + f[2] + f[4] + f[8] - ans[2] * 2 - ans[1] * 3 - ans[0] * 4;
    ans[4] = f[0] - ans[3] - ans[2] - ans[1] - ans[0];
    cout << ans[d] << endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

八卦天盘

如果不考虑“两个阴阳球不会经过相同的位置”的限制,那么我们可以枚举起点和终点的配对情况,算出对应的方案数和逆序对数量。其中某一种情况的方案数为每一对起点和终点之间的路径条数之乘积。

考虑上述限制,发现如果两个小球经过了同一点,它们之后能够走的情况是完全相同的,而在逆序对个数上奇偶存在差异,因此方案数之和为0,对答案不构成影响。

考虑上述暴力的过程,枚举所有排列,计算过程中的结果还与逆序对个数的奇偶性有关,与行列式的定义完全相同,因此只需要构造K阶行列式,其中第i行第j列的值为从第i个起点到第j个终点的路径条数。

  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
101
#include <bits/stdc++.h>
using namespace std;

#define N 605

long long d[N][N];
int n, m, p, k, in[N], out[N], head[N];
int cnt[N], vis[N], v1[N], v2[N];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[100005];

inline void add(int x, int y)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void getcnt(int x)
{
    if (vis[x]) return; vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        getcnt(edge[i].to), cnt[x] = (cnt[x] + cnt[edge[i].to]) % p;
}

long long power(long long a, int b)
{
    long long re = 1;
    while (b)
    {
        if (b & 1) re = re * a % p;
        a = a * a % p, b >>= 1;
    }
    return re;
}

int det(long long d[N][N], int n)
{
    int cnt = 0; long long re = 1;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = i; j < n; ++j)
            if (d[j][i]) { t = j; break; }
        if (t == -1) return 0;
        if (t != i) ++cnt;
        for (int j = 0; j < n; ++j)
            swap(d[i][j], d[t][j]);
        long long inv = power(d[i][i], p - 2);
        for (int j = i + 1; j < n; ++j)
            if (d[j][i])
            {
                long long temp = d[j][i] * inv % p;
                for (int k = i; k < n; ++k)
                    d[j][k] = (d[j][k] - temp * d[i][k] % p + p) % p;
            }
    }
    for (int i = 0; i < n; ++i)
        re = re * d[i][i] % p;
    return cnt & 1 ? p - re : re;
}

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 main()
{
    freopen("bagua.in", "r", stdin);
    freopen("bagua.out", "w", stdout);
    cin >> n >> m >> p;
    for (int x, y, i = 1; i <= m; ++i)
        x = read(), y = read(),
        add(y, x), ++out[x], ++in[y];
    for (int i = 1; i <= n; ++i)
        if (in[i] == 0) v1[k++] = i;
    for (int i = 1, t = 0; i <= n; ++i)
        if (out[i] == 0) v2[t++] = i;
    for (int i = 0; i < k; ++i)
    {
        memset(cnt, 0, sizeof cnt);
        memset(vis, 0, sizeof vis);
        cnt[v1[i]] = 1, vis[v1[i]] = 1;
        for (int j = 0; j < k; ++j)
            getcnt(v2[j]), d[i][j] = cnt[v2[j]];
    }
    cout << det(d, k) << endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

盈虚方田

直接上公式: 枚举最大公因数d,先不考虑p

如果不考虑p,我们可以预处理出的值,然后用前缀和就可以O(sqrt(n))求出单组解了。

考虑了p也很简单,因为2^19次方已经大于了范围,所以p最大是19,再大了跟19也没有区别,于是我们可以预处理出19种不同的前缀和就可以了。或者可以离线询问,按p排序,动态的把单纯度小于等于p的点加进去就行了。每次更改都重新维护一个前缀和(最多更改19次……),不嫌麻烦想动态维护写个树状数组也行就是多个log.

复杂度Tsqrt(n)+nlogn,树状数组就再多个log,也是能过的。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 500005

int test, n, m, c;
int tot, v[N], p[N], mu[N], f[N], bit[N];
long long ans[N];
vector<int> cp[25];

struct data
{
    int pos, c, n, m;
    data() {}
    data(int _pos, int _c, int _n, int _m)
    : pos(_pos), c(_c), n(_n), m(_m) {}
    bool operator <(const data &d) const { return c < d.c; }
} q[N];

void linear_shake(int n)
{
    mu[1] = 1, f[1] = 0;
    for (int i = 2; i < n; ++i)
    {
        if (!v[i]) p[++tot] = i, mu[i] = -1, f[i] = 1;
        for (int j = 1; i * p[j] < n; ++j)
        {
            v[i * p[j]] = true, f[i * p[j]] = f[i] + 1;
            if (i % p[j]) mu[i * p[j]] = -mu[i];
            else { mu[i * p[j]] = 0; break; }
        }
    }
    for (int i = 1; i < n; ++i)
        cp[f[i]].push_back(i);
}

void modify(int x, int y)
{
    for (int i = x; i < N; i += i & -i)
        bit[i] += y;
}

int getsum(int x)
{
    int re = 0;
    for (int i = x; i; i -= i & -i)
        re += bit[i];
    return re;
}

void update(int x)
{
    for (int i = 1; i * x < N; ++i)
        modify(i * x, mu[i]);
}

long long query(int n, int m)
{
    long long re = 0;
    if (n > m) swap(n, m);
    for (int i = 1, last = 0; i <= n; i = last + 1)
    {
        last = min(n / (n / i), m / (m / i));
        re += 1ll * (n / i) * (m / i) * (getsum(last) - getsum(i - 1));
    }
    return re;
}

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 main()
{
    freopen("field.in", "r", stdin);
    freopen("field.out", "w", stdout);
    cin >> test;
    linear_shake(N);
    for (int x, y, i = 1; i <= test; ++i)
        x = read(), y = read(), q[i] = data(i, min(read(), 20), x, y);
    sort(q + 1, q + test + 1);
    for (int i = 0; i <= 20; ++i)
    {
        for (int j = 0; j < (int)cp[i].size(); ++j)
            update(cp[i][j]);
        for (int j = 1; j <= test; ++j)
            if (q[j].c == i) ans[q[j].pos] = query(q[j].n, q[j].m);
    }
    for (int i = 1; i <= test; ++i)
        printf("%lld\n", ans[i]);
    return 0;
}