绝渡逢舟模拟赛 Ⅲ

2016.01.17 11:28 Sun| 73 visits oi_2016| 2016_竞赛日常| Text

期望问题

题目描述

平面内给定一N个点的凸包,问在内部或边缘随机选两个不同的格点,以其为对角线正方形的面积期望是多少。

输入格式

第一行一个整数N。

接下来N行每行2个整数x,y顺时针或逆时针描述凸包上的点。

输出格式

一个实数表示面积的期望,保留8位小数(相对误差小于10^-9即为正确)。

样例输入

3
0 0
5 5 5 0

样例输出

4.66666667

数据范围和注释

对于30%的数据,3<=n<=30,坐标的绝对值<=100;

对于60%的数据,3<=n<=100,坐标的绝对值<=3000;

对于100%的数据,3<=n<=10^5,坐标的绝对值<=10^6。

异或问题

题目描述

N个数字,要求选择M次,每次从N个数中选出两个数(Ai,Aj)(但不能和之前某次选择相同),此次选择的得分为Ai xor Aj。求最大得分。

输入格式

第一行包含两个整数N,M。

接下来一行共N个整数描述N个数字。

输出格式

输出一个整数,表示最大得分除以10^9+7的余数

样例输入

3 2
1 2 3

样例输出

5

数据范围和注释

对于20%的测试数据,N≤1000;

对于40%的测试数据,NM≤500000;

对于70%的测试数据,N≤10000;

对于100%的测试数据,N≤50000,0≤Ai≤10^9。

集合问题

题目描述

给定长度为N的数列A,长度为M的数列B,和素数P。生成N个集合,第i个集合:

  1. 首先,这个集合一开始只有一个元素"1"。
  2. 我们从这个集合中任意选出一个元素c,对于所有的j,如果(c*Ai^Bj)mod p不存在于当前的集合中,则将它加入当前集合。
  3. 重复步骤2,直到无法将任意元素加入集合。 求这n个集合的并集包含多少个数字。

输入格式

第一行输入三个正整数N,M,P 第二行N个整数描述数列A 第三行M个整数描述数列B。

输出格式

输出一个整数表示并集的规模。

样例输入

2 1 7
1 6
5

样例输出

2

数据范围和注释

对于30%的数据:1≤n≤10,1≤m≤10,2≤p≤10^5;

对于60%的数据:1≤n≤500,1≤m≤10^5,2≤p≤10^5;

对于100%的数据:1≤n≤10^4,1≤m≤10^5,1≤Bi≤10^9,2≤p≤ 10^9且p为质数,1≤ Ai<p。

题解

期望问题

两点之间正方形的大小等于两点间横、纵坐标差的平方和除以 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
#include <bits/stdc++.h>
using namespace std;

#define N 2000010
#define M 1000000

int n; long double c1[N], c2[N], num;

struct point
{
    int x, y;
    point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
} p[N];

long double solve()
{
    for (int i = 0; i <= M * 2; ++i)
        c1[i] = c2[i] = -1;
    for (int i = 1; i <= n; ++i)
    {
        if (p[i + 1].x > p[i].x) for (int j = p[i].x; j <= p[i + 1].x; ++j)
            c1[j] = p[i].y + 1.0 * (p[i + 1].y - p[i].y)
                        * (j - p[i].x) / (p[i + 1].x - p[i].x);
        if (p[i + 1].x < p[i].x) for (int j = p[i].x; j >= p[i + 1].x; --j)
            c2[j] = p[i].y + 1.0 * (p[i + 1].y - p[i].y)
                        * (j - p[i].x) / (p[i + 1].x - p[i].x);
    }
    long double sum = 0, sum2 = 0, re = 0; num = 0;
    for (int i = 0; i <= M * 2; ++i)
    {
        if (c1[i] < 0 && c2[i] < 0) continue;
        if (c1[i] > c2[i]) swap(c1[i], c2[i]);
        int cnt = floor(c2[i] + 1e-10) - ceil(c1[i] - 1e-10) + 1;
        sum2 = sum2 + sum * 2 + num; sum = sum + num;
        re += cnt * sum2; num += cnt;
    }
    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("square.in", "r", stdin);
    freopen("square.out", "w", stdout);
    cin >> n;
    for (int x, y, i = 1; i <= n; ++i)
        x = read(), y = read(), p[i] = point(x + M, y + M);
    p[n + 1] = p[1];
    long double ans = 0;
    ans += solve();
    for (int i = 1; i <= n + 1; ++i)
        swap(p[i].x, p[i].y);
    ans += solve();
    cout << fixed << setprecision(8) << ans / num / (num - 1) << endl;
    return 0;
}

异或问题

首先求出要统计入答案中的最小的异或值,对于每一个数字分别求出贡献,加和即可。

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

#define N 50005
#define mod 1000000007

struct node
{
    node *son[2]; int size, cnt[31];
    node() : size(0) { son[0] = son[1] = 0, memset(cnt, 0, sizeof cnt); }
};

int n, a[N], k; long long m, tot, ans;
node *root, *pos[N];

void insert(node *&pos, int c, int d)
{
    if (!pos) pos = new node(); ++pos->size;
    for (int i = 0; i <= d; ++i)
        pos->cnt[i] += c >> i & 1;
    if (d == -1) return;
    if (c >> d & 1) insert(pos->son[1], c, d - 1);
    else insert(pos->son[0], c, d - 1);
}

int getk(long long s, int d)
{
    long long sum = 0;
    if (d == -1)
    {
        for (int i = 1; i <= n; ++i)
            if (pos[i]) sum += pos[i]->size;
        tot += sum; return 0;
    }
    for (int i = 1; i <= n; ++i)
        if (pos[i] && pos[i]->son[(a[i] >> d & 1) ^ 1])
            sum += pos[i]->son[(a[i] >> d & 1) ^ 1]->size;
    if (sum >= s)
    {
        for (int i = 1; i <= n; ++i)
            if (pos[i]) pos[i] = pos[i]->son[(a[i] >> d & 1) ^ 1];
        return getk(s, d - 1) + (1 << d);
    }
    tot += sum;
    for (int i = 1; i <= n; ++i)
        if (pos[i]) pos[i] = pos[i]->son[a[i] >> d & 1];
    return getk(s - sum, d - 1);
}

long long query(node *pos, int c, int d)
{
    if (!pos) return 0;
    if (d == -1) return 1ll * pos->size * k;
    if (k >> d & 1)
        return query(pos->son[(c >> d & 1) ^ 1], c, d - 1);
    long long re = 0; int v = (c >> d & 1) ^ 1;
    if (pos->son[v])
    {
        re += 1ll * pos->son[v]->size * (k & (-1 << (d + 1)));
        re += 1ll * pos->son[v]->size * (1 << d);
        for (int i = 0; i < d; ++i)
            if (!(c >> i & 1))
                re += 1ll * pos->son[v]->cnt[i] << i;
            else
                re += 1ll * (pos->son[v]->size - pos->son[v]->cnt[i]) << i;
    }
    return re + query(pos->son[v ^ 1], c, d - 1);
}

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("xor.in", "r", stdin);
    freopen("xor.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        a[i] = read(), insert(root, a[i], 30), pos[i] = root;
    k = getk(2 * m, 30), ans = (2 * m - tot) * k;
    for (int i = 1; i <= n; ++i)
        ans = ans + query(root, a[i], 30);
    cout << ans / 2 % mod << endl;
    return 0;
}

集合问题

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

#define N 100005

map<int, int> mp; int blo, inv;
int n, m, p, g, a[N], b[N], sg, num[1000], f[1000], cnt;
vector<int> v;

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

int getroot(int p, int phi)
{
    for (int i = 1; i * i <= phi; ++i)
        if (phi % i == 0)
            num[++cnt] = i, i * i != phi ? num[++cnt] = phi / i : 0;
    sort(num + 1, num + cnt + 1);
    for (int i = 2; i < p; ++i)
        for (int j = 1; j <= cnt; ++j)
            if (j == cnt) return i;
            else if (power(i, num[j], p) == 1) break;
    return 0;
}

void prebsgs(int a, int p)
{
    blo = min(p - 1, 110000);
    for (int i = 0, t = 1; i < blo; ++i)
    {
        if (mp.find(t) == mp.end()) mp[t] = i;
        t = 1ll * t * a % p;
    }
    inv = power(g, p - blo - 1, p);
}

int bsgs(int b)
{
    for (int i = 0; i < blo; ++i)
    {
        if (mp.find(b) != mp.end())
            return i * blo + mp[b];
        b = 1ll * b * inv % p;
    }
    return -1;
}

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("set.in", "r", stdin);
    freopen("set.out", "w", stdout);
    cin >> n >> m >> p;
    prebsgs(g = getroot(p, p - 1), p);
    for (int i = 1; i <= n; ++i)
        a[i] = bsgs(read() % p);
    for (int i = 1; i <= m; ++i)
        b[i] = read();
    sg = b[1];
    for (int i = 2; i <= m; ++i)
        sg = __gcd(sg, b[i]);
    for (int i = 1; i <= n; ++i)
        v.push_back(__gcd(1ll * a[i] * sg % (p - 1), 1ll * p - 1));
    sort(v.begin(), v.end());
    for (int i = 1; i <= cnt; ++i)
        for (int j = 0; j < v.size(); ++j)
            if (num[i] % v[j] == 0) { f[i] = 1; break; }
    int ans = 0;
    for (int i = 1; i <= cnt; ++i)
    {
        ans += (p - 1) / num[i] * f[i];
        for (int j = i + 1; j <= cnt; ++j)
            if (num[j] % num[i] == 0) f[j] -= f[i];
    }
    cout << ans << endl;
    return 0;
}