8.06 没签上到的杭电6
1001-Road To The 3rd Building
题意
给定 n 个数，每个数有价值 val[i] 。随机选择 ileq j 的 (i,j) 点对，问下标 i 到 j 的子数组价值和的平均数的期望。
思路
当随机选择 1 个或者 n 个时，每个数只出现一次；随机选择 2 个或者 n-1 个时，除了首位的数出现一次，其他数出现两次……递推计算即可。总方案数是 n*(n 1)/2 。
代码
代码语言：javascript复制#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("%dn",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 ，kin Z^ 时满足条件。
代码
代码语言：javascript复制#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("Fn");
if((n-1)%k==0) return pf("Tn");
return pf("Fn");
}
int main(){
int _; sc(_); while(_--) solve();
}1010-Expectation
题意
给定 n 个点 m 条边，每条边有权值。定义一棵生成树的权值和为所有边权的按位与，问随机选定生成树的期望权值和是多少。
思路
将权值按位拆分，枚举二进制位计算。每次跑一遍矩阵树。
代码
代码语言：javascript复制// 队友板子
#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("%dn", ans);
return 0;
}
int main()
{
per(_,re,1) solve();
}
