hdu2021多校1

发表于 分类于 ，

链接

A

题意

给定 $n$，求 $(n\bmod1)\vee (n\bmod 2)\vee \cdots\vee (n\bmod n)$。

$T\le 5000$。

题解

打表题，可能的答案只能为 $2^k-1$。于是算出 $k$ 即可。

E

题意

一个 $2\sim n$ 标记的 $n-1$ 个点形成一个完全无向图，边 $i,j$ 的边权为 $\text{lcm}(i,j)$。求完全图的最小生成树边权和。

$n\le 10^7,T\le 100$。

题解

构造题，对于 $3\sim n$ 的点，质数则连 $2$，否则随便找个约数连即可。

于是线性筛预处理即可。

F

题意

一个序列，找到最短的序列使得区间异或和不小于 $k$，输出左端点最小时的情况。

$n\le 10^5,a_i < 2^{30}$。

题解

做前缀异或和，然后在Trie上操作即可。

G

题意

$n$ 个人传球，每次不能传给自己。刚开始在 $1$手上，设第 $x$ 次传球后在 $1$ 手上的情况为 $f_x$，求最小的 $x$ 使得 $f_x\equiv t\pmod {998244353}$。

题解

推出 $f_x$ 通项为 $\frac{n-1}{n}(-1)^i+\frac{1}{n}(n-1)^i$。

于是将 $i$ 分开奇偶讨论，BSGS即可。

时间复杂度 $O(T\sqrt{n})$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())

const ll mod=998244353;
const int w=sqrt(mod);
const ll inf=1e18;

inline ll Pow(ll x,int y)
{
	ll ans=1;
	for(;y;y>>=1,x=x*x%mod) if(y&1) ans=ans*x%mod;
	return ans;
}

const int m1=2333333;
vector<pii> has[m1];
int st[w+5],top;
int y;
inline void insert(ll x,int id)
{
	y=x%m1;
	has[y].pb(mp(x,id));
	st[++top]=y;
}
inline ll find(int x)
{
	y=x%m1;
	ll ans=-1;
	ff(i,0,(int)has[y].size()) if(x==has[y][i].fi) ans=max(ans,(ll)has[y][i].se);
	return ans;
}

inline ll solve(ll a,ll x)
{
	ll p=1;
	fo(i,0,w)
	{
		insert(p*a%mod,i);
		(p*=x)%=mod;
	}
	ll ans=inf;
	p=Pow(x,w);
	ll t=p;
	ll q;
	fo(i,1,w+1)
	{
		q=find(t);
		if(q!=-1) ans=min(ans,1ll*i*w-q);
		t=t*p%mod;
	}
	ff(i,1,top) has[st[i]].clear();
	top=0;
	return (ans==inf)?-1:ans;
}
ll n,x,a,b;
int main()
{
	CASET
	{
		n=read(); x=read();
		if(x==1) {printf("%d\n",0); continue;}
		if(x==0) {printf("%d\n",1); continue;}
		a=Pow(n,mod-2);
		b=a*(n-1)%mod;
		ll t=solve((x*n-(n-1)+mod)%mod,1ll*(n-1)*(n-1)%mod);
		if(t!=-1) t=t*2;
		ll q=solve((x*n+(n-1)+mod)%mod*(n-1)%mod,1ll*(n-1)*(n-1)%mod);
		if(q!=-1) q=q*2-1;
		if(t==-1) printf("%d\n",q);
		else if(q==-1) printf("%d\n",t);
		else printf("%d\n",min(q,t));
	}
}

I

题意

在一个二维坐标上，存在着 $n$ 个点 $(i,f_i)$。

多次询问某个平行于坐标轴的矩形中的点有多少个不同的横坐标。

$T\le 5$，$n,q\le 10^5$

题解

记 $a_i$ 表示点 $i$ 坐标向左看到的第一个点的横坐标，没有记为 $0$。

对于一个矩形，差分一下变成一条边在 $x$ 轴上的询问。左右区间为 $[l,r]$，高度为 $h$。

对于每个询问，查询 $l\le i\le r,a_i<l,f_i\le h$ 的个数。

这是一个三位偏序问题，cdq+树状数组即可。时间复杂度 $O(n\log ^2n)$。