暑假集训系列题解（十）
题目1
题目链接
题目描述
Given are integers N and M. How many sequences A of N integers satisfy the following conditions?
1≤Ai≤M(i=1,2,…,N)
Ai+1 is a multiple of Ai. (i=1,2,…,N−1)
Since the answer can be enormous, report it modulo 998244353.
Constraints
All values in input are integers.
1≤N≤2×$10^5$
1≤M≤2×$10^5$
输入
Input is given from Standard Input in the following format:
N M
输出
Print the answer.
样例输入
【样例1】
3 4
【样例2】
20 30
【样例3】
200000 200000样例输出
【样例1】
13
【样例2】
71166
【样例3】
835917264提示
样例1解释
Some of the sequences A satisfying the conditions follow:
A=(1,1,4)
A=(3,3,3)
A=(1,2,4)
题解
排列组合+质因数分解，枚举An的取值范围，即1-m，后对An进行质因数分解，对于每一个因子p，设其为e次幂，则对于p因子，可以放在n个位置上，模型转为将e个小球放到n个盒子中且盒子可以为空，则答案为$ \tbinom{n+e-1}{e}$
参考链接：
https://blog.csdn.net/weixin_43184669/article/details/116059248
代码
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll ksm(ll a,ll b)
{
ll ans1=1,ans2=a;
while(b!=0)
{
if(b%2)
ans1=(ans2*ans1)%mod;
ans2=(ans2*ans2)%mod;
b/=2;
}
return ans1;
}
ll inv[300500]= {0};
ll jc[300500]= {0};
ll C(ll a,ll b)
{
if(a==b)
return 1;
if(b>a||a==0)
return 0;
ll res=jc[a]*inv[b]%mod*inv[a-b]%mod;
return res;
}
int main()
{
jc[0]=1;
for(ll i=1; i<=300100; i++)
jc[i]=(jc[i-1]*i)%mod;
inv[300100]=ksm(jc[300100],mod-2);
for(ll i=300100-1; i>=1; i--)
inv[i]=inv[i+1]*(i+1)%mod;
ll n,m,ans=0;
cin>>n>>m;
for(ll i=1; i<=m; i++)
{
vector<ll>v;
ll tmp=i;
for(ll j=2; j*j<=tmp ; j++)
{
if(tmp%j!=0)
continue;
ll cnt=0;
while(tmp%j==0)
{
tmp/=j;
cnt++;
}
v.push_back(cnt);
}
if(tmp!=1)
v.push_back(1);
tmp=1;
for(int i=0; i<v.size(); i++)
tmp=(tmp*C(n+v[i]-1,v[i]))%mod;
ans=(ans+tmp)%mod;
}
cout<<ans<<endl;
}题目2
题目链接
题目描述
Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1 bidirectional roads, such that there is exactly one path between any two pastures. Bessie, a cow who loves her grazing time, often complains about how there is no grass on the roads between pastures. Farmer John loves Bessie very much, and today he is finally going to plant grass on the roads. He will do so using a procedure consisting of M steps (1 <= M <=100,000).
At each step one of two things will happen:
- FJ will choose two pastures, and plant a patch of grass along each road in between the two pastures, or,
- Bessie will ask about how many patches of grass on a particular road, and Farmer John must answer her question.
Farmer John is a very poor counter -- help him answer Bessie's questions!
输入
- Line 1: Two space-separated integers N and M
- Lines 2..N: Two space-separated integers describing the endpoints of
a road. - Lines N+1..N+M: Line i+1 describes step i. The first character of the line is either P or Q, which describes whether or not FJ is planting grass or simply querying. This is followed by two space-separated integers A_i and B_i (1 <= A_i, B_i <= N) which describe FJ's action or query.
输出
- Lines 1..???: Each line has the answer to a query, appearing in the same order as the queries appear in the input.
样例输入
4 6
1 4
2 4
3 4
P 2 3
P 1 3
Q 3 4
P 1 4
Q 2 4
Q 1 4样例输出
2
1
2题解
树链剖分，代码如下：
代码
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum[400500] = {0}, lazy[400500] = {0};
ll dep[200500] = {0}, size1[200500] = {0}, son[200500] = {0}, f[200500] = {0}, id[200500] = {0}, top[200500] = {0};
struct node
{
ll to, next;
};
node edge[400500] = {0};
ll head[400500] = {0};
ll num = 0, cnt = 0;
void add_edge(ll from, ll to)
{
edge[++num] = {to, head[from]};
head[from] = num;
}
void dfs1(ll now, ll fa)
{
size1[now] = 1;
for (ll i = head[now]; i; i = edge[i].next)
{
ll to = edge[i].to;
if (to == fa)
continue;
f[to] = now;
dep[to] = dep[now] + 1;
dfs1(to, now);
size1[now] += size1[to];
if (size1[to] > size1[son[now]])
son[now] = to;
}
}
void dfs2(ll now, ll fa)
{
id[now] = ++cnt;
top[now] = fa;
if (son[now])
dfs2(son[now], fa);
for (ll i = head[now]; i; i = edge[i].next)
{
ll to = edge[i].to;
if (to == f[now] || to == son[now])
continue;
dfs2(to, to);
}
}
void push_down(ll t, ll l, ll r)
{
if (lazy[t] == 0)
return;
lazy[2 * t + 1] += lazy[t];
lazy[2 * t] += lazy[t];
ll mid = (l + r) / 2;
sum[2 * t] += (mid - l + 1) * lazy[t];
sum[2 * t + 1] += (r - mid) * lazy[t];
lazy[t] = 0;
}
void push_up(ll t)
{
sum[t] = sum[2 * t] + sum[2 * t + 1];
}
void update(ll t, ll l, ll r, ll L, ll R, ll add)
{
if (l <= L && R <= r)
{
lazy[t] += add;
sum[t] += add * (R - L + 1);
return;
}
push_down(t, L, R);
ll mid = (L + R) / 2;
if (l <= mid)
update(2 * t, l, r, L, mid, add);
if (mid < r)
update(2 * t + 1, l, r, mid + 1, R, add);
push_up(t);
}
ll query(ll t, ll l, ll r, ll L, ll R)
{
if (l <= L && R <= r)
return sum[t];
push_down(t, L, R);
ll mid = (L + R) / 2;
ll ans = 0;
if (l <= mid)
ans += query(2 * t, l, r, L, mid);
if (mid < r)
ans += query(2 * t + 1, l, r, mid + 1, R);
return ans;
}
void update_chain(ll x, ll y)
{
ll fx = top[x], fy = top[y];
while (fx != fy) ///不在同一条重链上
{
if (dep[fx] < dep[fy])
swap(x, y), swap(fx, fy);
update(1, id[fx], id[x], 1, cnt, 1);
x = f[fx], fx = top[x]; ///跳转到另一条重链
}
if (id[x] > id[y])
swap(x, y);
update(1, id[x] + 1, id[y], 1, cnt, 1);
}
ll query_chain(ll x, ll y)
{
ll fx = top[x], fy = top[y], ans = 0;
while (fx != fy) ///不在同一条重链上
{
if (dep[fx] < dep[fy])
swap(x, y), swap(fx, fy);
ans += query(1, id[fx], id[x], 1, cnt);
x = f[fx], fx = top[x]; ///跳转到另一条重链
}
if (id[x] > id[y])
swap(x, y);
ans += query(1, id[x] + 1, id[y], 1, cnt);
return ans;
}
int main()
{
ll n, m, from, to;
scanf("%lld%lld", &n, &m);
for (ll i = 1; i <= n - 1; i++)
{
scanf("%lld%lld", &from, &to);
add_edge(from, to);
add_edge(to, from);
}
f[1] = 0, dep[1] = 1;
dfs1(1, 0), dfs2(1, 1);
char c[10];
for (ll i = 1; i <= m; i++)
{
scanf("%s%lld%lld", c + 1, &from, &to);
if (c[1] == 'P')
update_chain(from, to);
else
printf("%lld\n", query_chain(from, to));
}
}题目3
题目链接
题目
image-20210815164909213题解
树链剖分，将树上的点映射为线段树中的点，然后询问最大值和最小值即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> v[100500];
ll size1[100500] = {0}, id[100500] = {0}, fa[100500][30] = {0}, dep[100500] = {0}, tem[100500] = {0}, w[100500] = {0};
ll cnt = 0;
ll max1[400500] = {0}, min1[400500] = {0};
void dfs(ll now, ll fa1)
{
id[now] = ++cnt;
dep[now] = dep[fa1] + 1;
size1[now] = 1;
w[cnt] = tem[now];
fa[now][0] = fa1;
for (ll i = 1; (1 << i) <= dep[now]; i++)
fa[now][i] = fa[fa[now][i - 1]][i - 1];
for (ll i = 0; i < v[now].size(); i++)
{
ll to = v[now][i];
if (to == fa1)
continue;
dfs(to, now);
size1[now] += size1[to];
}
}
bool check(ll x, ll l, ll r)
{
if (x <= r && x >= l)
return 1;
return 0;
}
void push_up(ll t)
{
min1[t] = min(min1[2 * t], min1[2 * t + 1]);
max1[t] = max(max1[2 * t], max1[2 * t + 1]);
}
void build(ll t, ll l, ll r)
{
if (l == r)
{
max1[t] = min1[t] = w[l];
return;
}
ll mid = (l + r) / 2;
build(2 * t, l, mid);
build(2 * t + 1, mid + 1, r);
push_up(t);
}
ll query_sum(ll t, ll l, ll r, ll L, ll R, ll lt, ll rt) ///l,r为更新区间，L,R为线段树区间
{
if (min1[t] > rt || max1[t] < lt)
return 0;
else if (l <= L && R <= r)
{
if (check(max1[t], lt, rt) && check(min1[t], lt, rt))
return R - L + 1;
}
ll mid = (L + R) / 2, sum = 0;
if (l <= mid)
sum += query_sum(2 * t, l, r, L, mid, lt, rt);
if (mid < r)
sum += query_sum(2 * t + 1, l, r, mid + 1, R, lt, rt);
return sum;
}
int main()
{
ll n, from, to;
scanf("%lld", &n);
for (ll i = 1; i < n; i++)
{
scanf("%lld%lld", &from, &to);
v[from].push_back(to);
v[to].push_back(from);
}
for (ll i = 1; i <= n; i++)
scanf("%lld", &tem[i]);
dfs(1, 0);
build(1, 1, n);
ll x, l, r, q;
scanf("%lld", &q);
for (ll i = 1; i <= q; i++)
{
scanf("%lld%lld%lld", &x, &l, &r);
if (!check(tem[x], l, r))
{
puts("0");
continue;
}
for (int i = 21; i >= 0; i--)
{
int fa1 = fa[x][i];
if (fa1 != 0)
{
if (check(tem[fa1], l, r))
x = fa1;
}
}
printf("%lld\n", query_sum(1, id[x], id[x] + size1[x] - 1, 1, n, l, r));
}
}题目4
题目链接
题目描述
Farmer John has been taking an evening algorithms course at his local university, and he has just learned about minimum spanning trees. However, Farmer John now realizes that the design of his farm is not as efficient as it could be, and he wants to simplify the layout of his farm.
The farm is currently arranged like a graph, with vertices representing fields and edges representing pathways between these fields, each having an associated length. Farmer John notes that for each distinct length, at most three pathways on his farm share this length. FJ would like to remove some of the pathways on his farm so that it becomes a tree -- that is, so that there is one unique route between any pair of fields. Moreover, Farmer John would like this to be a minimum spanning tree -- a tree having the smallest possible sum of edge lengths.
Help Farmer John compute not only the sum of edge lengths in a minimum spanning tree derived from his farm graph, but also the number of different possible minimum spanning trees he can create.
输入
- Line 1: Two integers N and M (1 <= N <= 40,000; 1 <= M <= 100,000), representing the number of vertices and edges in the farm graph, respectively. Vertices are numbered as 1..N.
- Lines 2..M+1: Three integers a_i, b_i and n_i (1 <= a_i, b_i <= N; 1<= n_i <= 1,000,000) representing an edge from vertex a_i to b_i with length n_i. No edge length n_i will occur more than three times.
输出
- Line 1: Two integers representing the length of the minimal spanning tree and the number of minimal spanning trees (mod 1,000,000,007).
样例输入
4 5
1 2 1
3 4 1
1 3 2
1 4 2
2 3 2样例输出
4 3提示
Picking both edges with length 1 and any edge with length 2 yields a minimum spanning tree of length 4.
题解
最小生成树，分类讨论即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
struct node
{
int from, to, val;
};
node a[100500] = {0};
bool cmp(node a, node b)
{
return a.val < b.val;
}
int fa[100500] = {0};
int findfa(int n)
{
if (n == fa[n])
return n;
return fa[n] = findfa(fa[n]);
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d%d", &a[i].from, &a[i].to, &a[i].val);
for (int i = 1; i <= n; i++)
fa[i] = i;
sort(a + 1, a + m + 1, cmp);
ll ans = 0, sum = 1;
for (int i = 1; i <= m;)
{
int cnt = 0, num = 0;
set<pair<int, int>> s;
int j;
for (j = i; a[j].val == a[i].val && j <= m; j++)
{
int fx = findfa(a[j].from);
int fy = findfa(a[j].to);
if (fx > fy)
swap(fx, fy);
if (fx != fy)
{
cnt++;
s.insert({fx, fy});
}
}
for (; i < j; i++)
{
int fx = findfa(a[i].from);
int fy = findfa(a[i].to);
if (fx != fy)
{
num++;
fa[fx] = fy;
ans += a[i].val;
}
}
if (num == 1)
{
sum = sum * cnt % mod;
}
else if (num == 2)
{
if (cnt == 3 && s.size() == 2)
sum = sum * 2 % mod;
else if (cnt == 3 && s.size() == 3)
sum = sum * 3 % mod;
}
}
cout << ans << ' ' << sum << endl;
}题目5
题目链接
题目描述
Alice and Bob are playing a game.
They take turns to operate. There are n numbers, a1 , a2 , ... , an. Every time, the player plays in 3 steps.
1.Arbitrarily chooses one number ai.
2.Arbitrarily chooses another number x(1≤x<ai).
3.Replace the number ai with gcd(ai,x). Here, gcd(u,v) refers to the Greatest Common Divisor of u and v.
When a player can not make a single move he/she loses the game. Alice moves the first and she asks you to tell her who will win the game if both player play optimally.
输入
- The first line contains a number T(1≤T≤100), the number of testcases.
- For each testcase, there are two lines.
- The first line contains one number n(1≤n≤$10^6$).
- The second line contains n numbers a1 , a2 , ... , an(1≤ai≤$10^7$).
- It is guaranteed that for all testcases, ∑n≤$10^6$.
输出
- Line 1: Two integers representing the length of the minimal spanning tree and the number of minimal spanning trees (mod 1,000,000,007).
样例输入
2
1
1
1
2样例输出
Bob
Alice题解
尼尔博弈变形，求解质因数的个数。
代码
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const ll maxn=1e7+5;
ll low_prime[10050000]={0};
ll prime[700500]={0};
ll cnt=0;
int main()
{
for(ll i=2;i<=maxn;i++)
{
if(low_prime[i]==0)
{
low_prime[i]=i;
prime[++cnt]=i;
}
for(ll j=1;j<=cnt&&prime[j]*i<=maxn;j++)
{
low_prime[prime[j]*i]=prime[j];
if(i%prime[j]==0)
break;
}
}
ll t;
scanf("%lld",&t);
while(t--)
{
ll n,flag=0;
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
{
ll m,sum=0;
scanf("%lld",&m);
while(m>1)
{
m/=low_prime[m];
sum++;
}
flag^=sum;
}
if(!flag)
puts("Bob");
else
puts("Alice");
}
}