2020 Multi-University Training Contest 6

wenzhuan

发布于 2022-08-15 12:44:14

3550

发布于 2022-08-15 12:44:14

文章被收录于专栏：你会烧尽还是结冰

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 。

代码

#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^+ 时满足条件。

代码

#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 条边，每条边有权值。定义一棵生成树的权值和为所有边权的按位与，问随机选定生成树的期望权值和是多少。

思路

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

代码

// 队友板子
#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();
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

equation