2022-10-7总结

题目

$n \le 8$，考虑搜索，但是直接爆搜的计算次数最坏在 $32^8=2^{40}$ 级别，无法接受。

考虑平衡一下，使用折半搜索，然后用双指针合并答案，计算次数 $2^{20}$，可以通过。

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;
const int N = 10;
const int SIZE = 1.5e6+10;

int n, s, a[N];
ll tmp[2][SIZE];
int cnt[2], lim;

void dfs(int x, ll sum, int type);

int main()
{
    cin >> n >> s;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    
    lim = n/2, dfs(1, 0, 0);
    if(n != 1) lim = n, dfs(n/2+1, 0, 1);
    
    sort(tmp[0]+1, tmp[0]+cnt[0]+1);
    sort(tmp[1]+1, tmp[1]+cnt[1]+1);
    
    ll ans = 0;
    for(int i = cnt[0], j = 0; i >= 1; i--)
    {
        while(j < cnt[1] and tmp[0][i]+tmp[1][j+1] <= s) j++;
        ans += j;
    }
    
    cout << ans << "\n";
}

void dfs(int x, ll sum, int type)
{
    if(sum > s) return void();
    if(x > lim)
    {
        tmp[type][++cnt[type]] = sum;
        return void();
    }
    ll pw = a[x];
    for(; sum+pw <= s; pw *= a[x])
        dfs(x+1, sum+pw, type);
}

名字

树上距离: $dep(x)+dep(y)- 2dep(LCA)$

我们分别求出每一项的期望就行了。

$E(dep(x))$ 很好求，直接枚举父亲然后转移就行了:

$$E(dep(x)) = \frac{ \sum\limits_{fa=1}^{n} a_{fa}*(E(dep(fa))+b_i+b_{fa})}{ \sum_{i=1}^xa_i}$$

现在就是求 LCA 的期望了。

设 $x < y$，则 $E(dep(LCA))$ 只与 $x$ 有关，考虑 $y$ 一直向上跳，跳到第一个编号 $\le x$ 的点，这个点以正比于 $a$ 的概率在 $[1,x]$ 中随机。

如果跳到了 $x$，期望深度就是 $E(dep(x))$，否则设跳到的点是 $u$ ，期望深度就是 $E(dep(LCA(x,u)))$ , 用上面的方法递推就行。

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;
const int N = 3e5+10;
const int P = 1e9+7;

int n, q;
ll a[N], b[N];
ll sum[N], dep[N];
ll lca[N];

ll qpow(ll a, ll b);

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> a[i], sum[i] = sum[i-1]+a[i];
    for(int i = 1; i <= n; i++)
        cin >> b[i];
    
    for(ll i = 2, tmp = b[1]*a[1]; i <= n; i++)
    {
        dep[i] = (tmp*qpow(sum[i-1],P-2) + b[i]) % P;
        (tmp += (dep[i]+b[i])*a[i]%P) %= P;
    }
    for(ll i = 2, tmp = 0; i <= n; i++)
    {
        lca[i] = (dep[i]*a[i]+tmp)%P * qpow(sum[i], P-2)%P;
        (tmp += lca[i]*a[i]%P) %= P;
    }
    
    for(int i = 1; i <= q; i++)
    {
        int x, y; cin >> x >> y;
        if(x > y) swap(x, y);
        if(x == y)
            cout << "0\n";
        else
            cout << ((dep[x]+dep[y]-2*lca[x])%P+P)%P << "\n";
    }
}

ll qpow(ll a, ll b)
{
    ll ans = 1;
    for(; b; b >>= 1, a = a*a%P)
        if(b&1) ans = ans*a%P;
    return ans;
}