Butteruni Blog
0%

2023杭电暑期多校5（A，E，G，I，L）

发表于 更新于 分类于

题目链接

由易到难为：LAG，IE

L. Counting Stars

分别计算不同度数的点对答案的贡献，度数种类上限为 ，总时间复杂度 ，实际将将跑满时限。

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
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e6 + 10;
const long long MOD = 1e9 + 7;

long long n, m;
long long deg[MAXN], fact[MAXN];
map<long long, long long> cnt;

inline long long inv(long long a, long long b)
{
    long long res = 1;
    b -= 2;
    while(b)
    {
        if(b & 1)
            res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

// 先预处理出fact[]，即阶乘，inv()即费马小定理求逆元 m >= n
inline long long C(long long m, long long n, long long p)
{
    return m < n ? 0 : fact[m] * inv(fact[n], p) % p * inv(fact[m - n], p) % p;
}
inline long long lucas(long long m, long long n, long long p)
{
    return n == 0 ? 1 % p : lucas(m / p, n / p, p) * C(m % p, n % p, p) % p;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    fact[0] = 1;
    for(int i = 1; i <= MAXN-10; ++i)
    {
        fact[i] = (fact[i-1]*i) % MOD;
    }
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> m;
        for(int i =1 ; i<= n; ++i)
            deg[i] = 0;
        cnt.clear();
        for(int i = 1; i<= m; ++i)
        {
            int u, v;
            cin >> u >> v;
            ++deg[u];
            ++deg[v];
        }
        for(int i = 1; i <= n; ++i)
        {
            ++cnt[deg[i]];
        }
        long long ans = 0;
        for(long long k = 2; k < n; ++k)
        {
            long long res = 0;
            for(auto iter = cnt.lower_bound(k); iter != cnt.end(); ++iter)
            {
                res = (res + (*iter).second * lucas((*iter).first, k, MOD) % MOD) % MOD;
            }
            ans ^= res;
        }
        cout << ans << '\n';
    }
    return 0;
}

G. Expectation (Easy Version)

简单概率，即胜利概率为 ，失败概率为 ，则答案 预处理后复杂度 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 1e6 + 10;
ll fac[N],invfac[N];
ll qpow(ll a,ll b)
{
    if(a == 1)
        return 1;
    ll res = 1;
    while(b)
    {
        if(b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
    void init()
    {
        fac[0] = 1;
        for (int i = 1; i < N; ++i) 
            fac[i] = (fac[i - 1] * i) % mod;
        invfac[N - 1] = qpow(fac[N - 1],mod - 2);
        for (int i = N - 2; i >= 0; --i) 
            invfac[i] = (invfac[i + 1] * (i + 1)) % mod;
    }
    ll C(int n, int m)
    {
        if (n < m || m < 0) return 0;
        return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
    }
int t;
ll a,b,n,m;
ll pre[N];
ll pre2[N];
ll pre1[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> t;
    init();
//     cout << invfac[2] << endl;
    while(t--)
    {
        cin >> n >> m >> a >> b;
        ll win_p = a * qpow(b,mod - 2) % mod;
        ll lose_p = (b - a) * qpow(b,mod -  2) % mod;
//         cout << win_p << " " << lose_p << endl;
        for(int i = 1;i <= n;++i)
        {
            pre[i] = qpow(i,m);
        }
        for(int i = 2;i <= n;++i)
        {
            pre[i] = (pre[i - 1] + pre[i]) % mod;
        }
        pre1[0] = pre2[0] = 1;
        for(int i = 1;i <= n;++i)
        {
            pre1[i] = win_p;
            pre2[i] = lose_p;
            if(i != 1)
            {
                pre1[i] = (pre1[i] * pre1[i - 1] + mod) % mod;
                pre2[i] = (pre2[i] * pre2[i - 1] + mod) % mod;
            }
        }
        ll ans = 0;
        for(int i = 1;i <= n;++i)
        {
            ans = (ans + ((C(n,i) * pre1[i] % mod) * pre2[n - i] % mod) * pre[i] % mod + mod) % mod;
        }
        cout << ans << "\n";
    }
}

A. Typhoon

暴力枚举避难点到台风路径的最短距离即可，时间复杂度 。

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 10100;
int sgn(double x)
{
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    else return 1;
}
double sqr(double x){ return x * x;}
struct Point
{
    double x,y;
    Point(){};
    Point (double _x, double _y)
    {
        x = _x,y = _y;
    }
    bool operator == (const Point b)
    {
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    bool operator < (const Point b)
    {
        return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0:x < b.x;
    }
    Point operator -(const Point b)
    {
        return Point(x - b.x,y - b.y);
    }
    Point operator +(const Point b)
    {
        return Point(x + b.x,y + b.y);
    }
    Point operator *(const double k)
    {
        return Point(x * k,y * k);
    }
    Point operator /(const double k)
    {
        return Point(x / k,y / k);
    }
    double operator ^(const Point b)
    {
        return x * b.y - y * b.x;
    }
    double operator *(const Point b)
    {
        return x * b.x + y * b.y;
    }
    double operator ^(const Point &b)const
    {
        return x * b.y - y * b.x;
    }
    double len()
    {
        return sqrt(x * x + y * y);
    }
    double len2()
    {
        return x * x + y * y;
    }
    double dis(const Point b)
    {
        return sqrt((x - b.x) * (x - b.x) + (y - b.y) * (y - b.y));
    }
    double rad(Point a,Point b)
    {
        Point p = *this;
        return fabs(atan2(fabs((a - p) ^ (b - p)),(a - p) * (b - p)));
    }
    Point trunc(double r)
    {
        double l = len();
        if(!sgn(l))
            return *this;
        r /= l;
        return Point(x * r,y * r);
    }
};
typedef Point Vec2;
struct Line
{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e)
    {
        s = _s,e = _e; 
    }
    bool operator ==(const Line v)
    {
        return (s == v.s) && (e == v.e);
    }
    Line (Point p,double angle)
    {
        s = p;
        if(sgn(angle - pi / 2) == 0)
        {
            e = (s + Point(0,1));
        }else 
        {
            e = (s + Point(1,tan(angle)));
        }
    }
    Line(double a,double b,double c)
    {
        if(sgn(a) == 0)
        {
            s = Point(0,-c / b);
            e = Point(1,-c / b);
        }else if(sgn(b == 0))
        {
            s = Point(-c / a,0);
            e = Point(-c / a,1);
        }
        else
        {
            s = Point(0,-c / b);
            e = Point(1,(-c - a) / b);
        }
    }
    void adjust()
    {
        if(e < s)
            swap(s,e);
    }
    bool pointonseg(Point p)
    {
        return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) ^ (p - e)) <= 0;
    }
    double length()
    {
        return s.dis(e);
    }
    bool paraller(Line v)
    {
        return sgn((e - s)^(v.e - v.s)) == 0;
    }
    double dispointtoline(Point p)
    {
        return fabs((p - s) ^ (e - s)) / length();
    }
    double dispointtoseg(Point p)
    {
        if(sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0)
        {
//             printf("1 ");
            return min(p.dis(s),p.dis(e));
        }
//         printf("2 ");
        return dispointtoline(p);
    }
};  
Point make_circle(Point a,Point b,Point c) //三点共圆确定圆心
{
    double a1 = b.x - a.x, b1 = b.y - a.y,c1 = (a1 * a1 + b1 * b1) / 2;
    double a2 = c.x - a.x, b2 = c.y - a.y,c2 = (a2 * a2 + b2 * b2) / 2;
    double d = a1 * b2 -a2 * b1;
    return Point(a.x + (c1 * b2 - c2 * b1) / d,a.y+(a1 * c2 - a2 * c1) / d);
}
double Cross(Point A, Point B)///叉积计算
{
    return A.x * B.y - A.y * B.x;
}
bool inter(Line l1,Line l2)
{
    return 
    max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&
    max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&
    max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&
    max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&
    sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s)) <= 0 &&
    sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s)) <= 0;
}
Point shleter[maxp],typhoon[maxp];
Line lines[maxp];
int main()
{
    int n,m;
    scanf("%d %d",&m,&n);
    for(int i = 1;i <= m;++i)
    {
        scanf("%lf %lf",&typhoon[i].x,&typhoon[i].y);
//         printf("%lf %lf\n",typhoon[i].x ,typhoon[i].y);
    }
    for(int i = 1;i <= n;++i)
    {
        scanf("%lf %lf",&shleter[i].x,&shleter[i].y);
    }
    for(int i = 1;i < m;++i)
    {
        lines[i] = Line(typhoon[i],typhoon[i + 1]);
    }
    for(int i = 1;i <= n;++i)
    {
        double mn = 1e18;
        for(int j = 1;j < m;++j)
        {
            double temp = lines[j].dispointtoseg(shleter[i]);
            mn = min(mn,temp);
        }
        printf("%.4lf\n",mn);
    }
}

I. Tree

暴力走完整棵树即可，每次更新树的最大深度。

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e6 + 10;

struct Edge
{
    int to, next;
}edge1[MAXN], edge2[MAXN],edge3[MAXN];
struct Node
{
    ll fath, son1;
}node[MAXN];
struct HNode
{
    ll num, dep;
}hnode[MAXN];
bool vis[MAXN];
int cnt1, cnt2, cnt3;
int head1[MAXN], head2[MAXN];
Node q[MAXN<<2];
int read()
{
    int res = 0, ng = 1;
    char ch = getchar();
    // 处理符号和空格
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') ng = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        res = (res<<1) + (res<<3) + ch-48;
        ch = getchar();
    }
    return res * ng;
}
inline void add1(int from, int to)
{
    edge1[++cnt1].to = to;
    edge1[cnt1].next = head1[from];
    head1[from] = cnt1;
}
inline void add2(int from, int to)
{
    edge2[++cnt2].to = to;
    edge2[cnt2].next = head2[from];
    head2[from] = cnt2;
}
long long n, ans = 0;
void dfs(ll u,ll depth)
{
    int sz = 1;
    if(!vis[u])
    {
        for(int i = head1[u];i != -1;i = head1[edge1[i].to])
        {
            sz++;
        }
    }
    int x = 0 ;
    while((1 << x) < sz)
    {
        x++;
    }
    for(int k = head2[u];k != -1;k = edge2[k].next)
    {
        dfs(edge2[k].to,depth + x + 1);
    }
    for(int i = head1[u];i != -1;i = head1[edge1[i].to])
    {
        int j = edge1[i].to;
        for(int k = head2[j];k != -1;k = edge2[k].next)
        {
            dfs(edge2[k].to,depth + x + 1);
        }
    }
    ans = max(ans,depth + x + 1);
}
int main()
{
    int size(512<<20); // 512M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size)); // YOUR CODE
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // freopen("in", "r", stdin);
    int t;
    cin >> t;
    while(t--)
    {
        ans = 0;
        cnt1 = 0, cnt2 = 0, cnt3 =0;
        cin >> n;
        for(int i = 1; i <= n; ++i)
        {
            int fath;
            cin >> fath;
            vis[i] = 0;
            head1[i] = -1, head2[i] = -1;
            node[i].fath = fath;
        }
        for(int i = 1; i <= n; ++i)
        {
            int son;
            cin >> son;
            if(son)
            {
                node[i].son1 = son;
                add1(i, son);
            }
        }
        for(int i = 1; i <= n; ++i)
        {
            if(node[node[i].fath].son1 != i)
                add2(node[i].fath, i);
        }
        dfs(1, 0);
        cout << ans << '\n';
    }
    exit(0);
    // return 0;
}

E. Snake

容斥原理经典题，记 为有 个盒子中蛇的个数大于 ，总答案为

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 1000000;
ll fac[N + 10],invfac[N + 10];
ll qpow(ll a,ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)
        {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init()
{
    fac[0] = 1;
    for (int i = 1; i <= N; ++i) 
        fac[i] = (fac[i - 1] * i) % mod;
    invfac[N - 1] = qpow(fac[N - 1],mod - 2);
    for (int i = N - 2; i >= 0; --i) 
        invfac[i] = (invfac[i + 1] * (i + 1)) % mod;
}
ll C(int n, int m)
{
    if (n < m || m < 0) return 0;
    return fac[n] * invfac[m] % mod*invfac[n - m] % mod;
}
ll n,m,k;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> m >> k;
        ll ans = 0;
        for(int i = 0;i <= m;++i)
        {
            if(i & 1)
            {
                ans = ((ans - C(m,i) * C(n - i * k - 1,m - 1) % mod) % mod + mod) % mod;
            }else 
            {
                ans = (ans + C(m,i) * C(n - i * k - 1,m - 1) % mod) % mod;
            }
            if(ans < 0)
                ans += mod;
            else 
                ans %= mod;
        }
//         cout << ans << ' ';
        ans = (ans * fac[n]) % mod;
        ans = (ans * invfac[m]) % mod;
        cout << ans << '\n';
    }
    return 0;
}