2020 Multi-University Training Contest 6

本文总阅读量次

8.06 没签上到的杭电6

1001-Road To The 3rd Building

题意

给定 $n$ 个数，每个数有价值 $val[i]$ 。随机选择 $i\leq j$ 的 $(i,j)$ 点对，问下标 $i$ 到 $j$ 的子数组价值和的平均数的期望。

思路

当随机选择 $1$ 个或者 $n$ 个时，每个数只出现一次；随机选择 $2$ 个或者 $n-1$ 个时，除了首位的数出现一次，其他数出现两次……递推计算即可。总方案数是 $n*(n+1)/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
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
using namespace std;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7; 
int val[maxn],sum;
int qpow(int a,int b){
    int ans=1; while(b>0){
        if(b&1) ans=1ll*ans*a%mod;
        b>>=1; a=1ll*a*a%mod;
    } return ans;
}
int solve(){
    int n,ans(0),sum(0); sc(n); rep(i,1,n+1){
        sc(val[i]); sum+=1ll*val[i];
        if(sum>=mod) sum-=mod;
    } int l=1,r=n,t=sum,q=sum; while(l<=r){
        ans+=1ll*t*qpow(l,mod-2)%mod;
        if(ans>=mod) ans-=mod;
        if(l==r) break;
        ans+=1ll*t*qpow(r,mod-2)%mod;
        if(ans>=mod) ans-=mod;
        q=q-val[l]-val[r];
        while(q<0) q+=mod;
        t=t+q,l++,r--;
        if(t>=mod) t-=mod;
    } int u=1ll*n*(n+1)/2%mod;
    ans=1ll*ans*qpow(u,mod-2)%mod;
    return pf("%d\n",ans);
}
int main(){
    int _; sc(_); while(_--) solve();
}

1002-Little Rabbit’s Equation

题意

给定公式，格式为数字 运算符 数字 等于号 数字，问能否在 $2-16$ 的进制中找到满足此公式的进制。

思路

因为最多只有 $16$ 进制，故暴力枚举即可。找到式子中最大的数，从 $mx+1$ 进制枚举到 $16$ 进制。处理出三个数字在每个进制下的表示，满足条件的就输出。注意会爆 $int$ 。

1009-Divisibility

题意

给定数 $b$ 、$x$ ，问在 $b$ 进制下的任意 $y$ ，能否满足各位和是 $x$ 的倍数和 $y$ 是 $x$ 的倍数是充要条件。

思路

存在 $k*x+1=b$ ，$k\in Z^+$ 时满足条件。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
using namespace std;
typedef long long ll;
int solve(){
    ll n,k; scl(n); scl(k);
    if(k>=n) return pf("F\n");
    if((n-1)%k==0) return pf("T\n");
    return pf("F\n");
}
int main(){
    int _; sc(_); while(_--) solve();
}

1010-Expectation

题意

给定 $n$ 个点 $m$ 条边，每条边有权值。定义一棵生成树的权值和为所有边权的按位与，问随机选定生成树的期望权值和是多少。

思路

将权值按位拆分，枚举二进制位计算。每次跑一遍矩阵树。

代码

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
// 队友板子
#include <bits/stdc++.h>
#define re read()
#define ll long long
#define mkp(a, b) make_pair(a, b)
#define mst(a, c) memset(a, c, sizeof(a))
#define rep(a, b, c) for(int a = b; a <= c; a++)
#define per(a, b, c) for(int a = b; a >= c; a--)
using namespace std;
const int MOD = 998244353;
int read()
{
    int num = 0; bool f = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {f = (ch == '-'); ch = getchar();}
    while(ch >= '0' && ch <= '9') {num = (num << 1) + (num << 3) + ch - '0'; ch = getchar();}
    return f? -num : num;
}
struct SF
{
    int u, v, w;
}e[10005];
ll qpow(ll a, ll b)
{
    ll ans = 1;
    while(b > 0)
    {
        if(b & 1) ans = ans * a % MOD;
        b >>= 1; a = a * a % MOD;
    }
    return ans;
}
int n, m, cnt;
char str[15][15];
ll a[115][115];
void init(ll x, int ff)
{
    mst(a, 0);
    rep(i, 1, m)
    {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if(ff || x & w)
        {
            a[u][v]--, a[u][u]++;
            a[v][u]--, a[v][v]++;
        }
        
    }
}
ll det(int x)
{
    rep(i, 1, x) rep(j, 1, x) a[i][j] = (a[i][j] + MOD) % MOD;
    ll res = 1, f = 1;
    rep(i, 1, x)
    {
        rep(j, i + 1, x)
        {
            ll A = a[i][i], B = a[j][i];
            while(B)
            {
                ll tmp = A / B; A %= B; swap(A, B);
                rep(k, i, x) a[i][k] = (a[i][k] - tmp * a[j][k] % MOD + MOD) % MOD;
                rep(k, i, x) swap(a[i][k], a[j][k]); 
                f = -f;
            } 
        }
        if(!a[i][i]) return 0;
        res = (res * a[i][i]) % MOD;
    }
    if(f == -1) return (MOD - res) % MOD;
    return res;
}
int solve()
{
    n = re, m = re;
    rep(i, 1, m){
        e[i].u = re, e[i].v = re, e[i].w = re;
    }
    ll x = 1, ans = 0;
    rep(i, 0, 31){
        init(x, 0);
        ans += 1ll * det(n - 1) * x % MOD;
        if(ans >= MOD) ans -= MOD;
        x = x * 2;
    }
    init(0, 1);
    ll tt = det(n - 1);
    tt = qpow(tt, MOD - 2);
    ans = 1ll * ans * tt % MOD;
    printf("%d\n", ans);     
    return 0;
}
int main()
{
    per(_,re,1) solve();
}