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();
}