D、数列求和(嘤雄难度) J、滑稽树下你和我 I、滑稽树上滑稽果

D、数列求和(嘤雄难度)

1、 

2、

3、考虑先求出  的所有质因数，然后通过容斥来求所有与  不互质的  的和。

4、假设当前容斥算的质数是  ，那么就有  个该质数的倍数，即要求 

，式子化简得，求和公式再化简即可在时间内算出结果。

Code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
vector<ll>v;
ll power(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
void get(ll k)
{
	for (int i = 2; i * i <= k; i++)
	{
		if (k % i == 0)
		{
			v.push_back(i);
			while (k % i == 0)
				k /= i;
		}
	}
	if (k > 1)
		v.push_back(k);
}
ll n, m;
ll inv2 = power(2, mod - 2);
ll inv6 = power(6, mod - 2);
ll calc(ll k)
{
	ll cnt = n / k;
	ll res = ((k * k % mod) * (cnt * (cnt + 1) % mod) % mod) * ((2 * cnt + 1) * inv6 % mod) % mod + (cnt * (cnt + 1) % mod) * (k * inv2 % mod) % mod;
	return res % mod;
}
int main()
{
	while (scanf("%lld%lld", &n, &m) > 0)
	{
		v.clear();
		get(m);
		int sz = v.size();
		ll ans = 0;
		for (int i = 0; i < (1 << sz); i++)
		{
			int num = 1, cishu = 0;
			for (int j = 0; j < sz; j++)
			{
				if (i & (1 << j))
				{
					num *= v[j];
					cishu++;
				}
			}
			if (cishu & 1)
				ans = (ans - calc(num) + mod) % mod;
			else
				ans = (ans + calc(num)) % mod;
		}
		printf("%lld\n", ans);
	}
}

J、滑稽树下你和我

计算每条边的贡献，即两边点的个数的乘积，然后再乘这条边的长度，总和就是答案

Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 5;
const ll mod = 1e9 + 7;
struct edge
{
    int to;
    ll w;
    int nex;
}e[MAXN * 2];
int head[MAXN], tot = 1;
void add(int a, int b, ll c)
{
    e[tot] = edge{ b,c,head[a] };
    head[a] = tot++;
}
int num[MAXN], n;
bool vis[MAXN];
void init()
{
    memset(head, -1, sizeof(head));
    tot = 1;
}
ll ans = 0;
#define Pair pair<int,int>
map<Pair,ll>mp;
void dfs(int u, int fa)
{
    num[u] = 1;
    for (int i = head[u]; i + 1; i = e[i].nex)
    {
        int v = e[i].to;
        if (v != fa)
        {
            dfs(v, u);
            num[u] += num[v];
            ll ad = 1LL * (n - num[v]) * num[v] % mod;
            if (u < v)
                ad *= mp[Pair{ u,v }];
            else
                ad *= mp[Pair{ v,u }];
            ad %= mod;
            ans = (ans + ad) % mod;
        }
    }
}
int main()
{
    init();
    int a, b;
    ll c;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d%lld", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
        if (a > b)
            swap(a, b);
        mp[Pair{ a,b }] = c;
    }
    dfs(1, 0);
    printf("%lld\n", ans);
}

I、滑稽树上滑稽果

莫队算法，考虑将所求的作为单独一项 即  ，为了方便，下面将使用  来表示 。

预处理阶乘和阶乘的逆元

Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int MAXN = 1e5 + 5;
struct node
{
	int index;
	int n;
	int m;
}in[MAXN];
int id[105];
ll fac[MAXN], inv[MAXN];
ll ans[MAXN];
ll power(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
void init()
{
	fac[0] = fac[1] = 1;
	for (int i = 2; i < MAXN; i++)
		fac[i] = fac[i - 1] * i % mod;
	inv[0] = inv[1] = 1;
	inv[100000] = power(fac[100000], mod - 2);
	for (int i = 99999; i > 1; i--)
		inv[i] = inv[i + 1] * (i + 1) % mod;
}
ll comb(ll a, ll b)
{
	if (a < b || b < 0)
		return 0;
	ll res = fac[a] * inv[b] % mod * inv[a - b] % mod;
	return res;
}
ll inv2 = (mod + 1) / 2;
int unit;
int main()
{
	init();
	int num;
	scanf("%d", &num);
	for (int i = 0; i < num; i++)
	{
		in[i].index = i;
		scanf("%d%d", &in[i].n, &in[i].m);
	}
	unit = sqrt(num);
	sort(in, in + num, [](node q, node w) {
		if (q.n / unit == w.n / unit)
			return q.m < w.m;
		return q.n < w.n;
	});
	int a = 0, b = -1;
	ll res = 0;
	for (int i = 0; i < num; i++)
	{
		while (a < in[i].n)
		{
			res = (res * 2 - comb(a, b) + mod) % mod;
			a++;
		}
		while (a > in[i].n)
		{
			res = ((res + comb(a - 1, b)) % mod * inv2) % mod;
			a--;
		}
		while (b < in[i].m)
		{
			res = (res + comb(a, b + 1)) % mod;
			b++;
		}
		while (b > in[i].m)
		{
			res = (res - comb(a, b) + mod) % mod;
			b--;
		}
		ans[in[i].index] = res * power(inv2, in[i].n) % mod;
	}
	for (int i = 0; i < num; i++)
		printf("%lld\n", ans[i]);
}