20200602模拟-xgc

xgc的场

赛况大概是,rose100+40+65,其他基本是70+40+0(不考虑六中车队上个月做过C原题),然后我T1理解错题爆成全场垫底了qwq

赛后不限时补题:100+100+0

A

题意:有K种箱子,上面写着一个区间,每种无限个,现在选出n个箱子;然后给出m组物品,每组有2n个物品,物品上有数字,每组都恰将两个物品分配给一个箱子。最后统计每个箱子,记该方案的权值为,箱子中每个数到区间的最短距离($max(0,l-a,a-r)$),求最小权值,$nm,k \le 2e5$

请先思考后再展开

首先,猜测+感性证明,每组应该把第$2i-1和 2i$小的两个物品配对,于是把每组这两个放到第i个vc中,得到$O(nmk)$做法

再感受一波,把箱子按左端点排序后,vc对箱子编号的选择具有决策单调性,经典分治即可,深度为logn,二分优化下求mid的过程(预处理前后缀和),这样每层是klogm的

冲一发发现能过拍,$O(nmlogn+klogn*logm)$

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
int h[N],n,m,k;pii a[N];ll ans[N];int pos[N];
vc<ll> b[N],pre[N],suf[N];
ll calc(int i,int j)
{
ll ret=0;
int tl=lower_bound(all(b[i]),a[j].FR)-b[i].begin();if(tl>0) ret+=1ll*a[j].FR*tl-pre[i][tl-1];
int tr=lower_bound(all(b[i]),a[j].SE)-b[i].begin();if(tr<2*m) ret+=suf[i][tr]-1ll*a[j].SE*(m*2-tr);
return ret;
}
void solve(int l,int r,int gl,int gr)
{
if(l>r) return;
if(gl==gr){ fo(i,l,r) pos[i]=gl,ans[i]=calc(i,gl);return; }
int mid=(l+r)/2;fo(j,gl,gr){ ll now=calc(mid,j);if(now<ans[mid]) ans[mid]=now,pos[mid]=j; }
solve(l,mid-1,gl,pos[mid]),solve(mid+1,r,pos[mid],gr);
}
void main()
{
m=qread(),n=qread(),k=qread();fo(i,1,k) a[i].FR=qread(),a[i].SE=qread();sort(a+1,a+k+1);
fo(j,1,m)
{
fo(i,1,n+n) h[i]=qread();sort(h+1,h+n+n+1);
fo(i,1,n) b[i].PB(h[i*2-1]),b[i].PB(h[i*2]);
}
fo(i,1,n)
{
sort(all(b[i]));
pre[i]=b[i];fo(j,1,m*2-1) pre[i][j]+=pre[i][j-1];
suf[i]=b[i];fd(j,m*2-2,0) suf[i][j]+=suf[i][j+1];
}
mem(ans,0x3f);solve(1,n,1,k);
ll ANS=0;fo(i,1,n) ANS+=ans[i];write(ANS);
}

因为如果一个区间被包含了,那一定没意义,所以剩下区间都互不包含,则左端点排序后右端点也是递增的,所以我们在分治的时候,二分出一个位置,剩下的只需要移动指针就好了,这样就变成$O(nmlogn+klogn+nlogm)$

B

题意:n个点的完全图,定义$dis(x,y)=f(xy)$,其中$f(x)$为使$f(x)*x$为完全平方数的最小正整数

求$\sum_{1 \le a<b \le n} dis(a,b)$对998244353取模,$n \le 1e10$

请先思考后再展开

设$h(x)=x去掉平方因子后的数$,很容易发现,$dis(a,b)$一定是先把$h(a)$多的因子去掉,再补上比$h(b)$缺少的因子,因此两点最短路就是,$h(x)$的质因子集合做异或,剩下因子之和

那么我们枚举每个质数p去考虑其贡献,记$s=h(x)含p$的个数,则贡献为$s*(n-s)*p$,其中$s=\sum_{i=1}^{\infty} (-1)^{i+1} \lfloor n/p^i \rfloor$

另外需要特别计算的是$h(x)$相等的z个数,这样的数对距离为1,贡献为$C_z^2$,其中$z=\lfloor \sqrt{ n/x } \rfloor$,要求$\mu(x) \ne 0$

对于第二部分,还是整除分块,那么等价于求区间$\mu(x)^2$,经典问题,见OI之路-积性函数一章,$O(n^{3/4})$

对于第一部分,根号分治,$p \le \sqrt n$暴力计算,否则就是$\lfloor n/p \rfloor(n-\lfloor n/p \rfloor)*p$,左边整除分块一下,就是要求区间素数个数

区间形如$( \frac{n}{n/x}, \frac{n}{n/y} ]$,求前缀和访问的下标形如$ \lfloor \frac{n}{x} \rfloor$,可以min25筛,$O(\frac{n^{3/4}}{log})$

另外,如果把第二部分丢到OEIS上跑,可以得到A132345,总之答案为$\sum_x phi(x)\frac{n}{x^2}$,这样就能跑得飞快(不会证

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
const int N=1e5+10;
bool nop[N];int prn,prm[N],mu[N];ll S[N];
void pre()
{
mu[1]=1;
fo(i,2,N-1)
{
if(!nop[i]) prm[++prn]=i,mu[i]=-1,S[prn]=S[prn-1]+i;
for(int j=1;j<=prn and prm[j]*i<N;j++)
{
int t=prm[j]*i;nop[t]=1;
if(i%prm[j]==0) break; else mu[t]=-mu[i];
}
}
}
ll f[N<<1];ll M;
#define id(x) ((x)<=N?(x):N+M/(x))
void solve(ll _M)
{
M=_M;mem(f,0);vc<ll> num;for(ll i=1;i<=M;i++) num.PB(M/i),i=M/(M/i);//降序
for(auto n:num) f[id(n)]=(n+1)%MOD*(n%MOD)%MOD*invm(2)%MOD;
fo(j,1,prn) for(auto n:num)
{
if(prm[j]>n/prm[j]) break;
add(f[id(n)],MOD-(f[id(n/prm[j])]+MOD-S[j-1]-1)*prm[j]%MOD );
}
}
ll getmu(ll n){ ll sum=0;for(int i=1;i<=n/i;i++) sum+=(n/i/i)*mu[i];return sum; }
//------------------FIXED------------------
void main()
{
ll n=qread();pre();solve(n);
ll ans=0;fo(i,1,prn) if(prm[i]<=n/prm[i])
{
ll s=0;for(ll z=1,now=1;now<=n/prm[i];now=now*prm[i],z++) s+=n/now/prm[i]%MOD*(z&1?1:-1);
add(ans, (n-s)%MOD*(s%MOD)%MOD*prm[i]%MOD );
}
for(ll l=1,r,lstpre=0;l<=n;l++){
r=n/(n/l);
ll pre=getmu(r),v=(ll)sqrt(n/l)%MOD;
v=v*(v+MOD-1)%MOD*invm(2)%MOD;
add(ans, (pre-lstpre)%MOD*v%MOD );
v=f[id(r)];if(l>1) add(v,MOD-f[id(l-1)]);
if(l>n/l) add(ans, (n-n/l)%MOD*(n/l%MOD)%MOD*v%MOD );
l=r,lstpre=pre;
} write(ans);
}

C

题意:给n个带标号球,每个球有权值,统计合法排列,使得相邻两个球的乘积不超过w

对998244353取模,$n \le 2e3,0 \le |a_i|,w \le 1e9$

请先思考后再展开

先考虑$a_i \ge 0$:

排列的经典计数方法是,维护一个排列,按照一个确定的顺序去插入

考虑是怎样的顺序会方便,人类智慧想到一种顺序,将每种球分成A类和B类,其中A类要求后面插入的与自己乘积不超过w,B类要求后面插入的与自己乘积超过w

直觉根号分治,显然$i^2>w$的基本都是B类,$i^2 \le w$的基本都是A类

从后往前考虑,对于$i^2>w$,必须将$>w/i$的放自己后面。这很好搞,递增枚举i(排个序),每次把新的满足的全部放后面

得到顺序后,我们不再关心具体是什么数,变成了只有A、B的操作序列

B旁边不能再插东西,因此放B相当于填满即减少空位,放A相当于增加一个空位,递推即可

1
2
3
4
int n=qread(),w=qread();fo(i,1,n){ int num=qread();if(1ll*num*num<=w) A.PB(num); else B.PB(num); }
sort(all(A)),sort(all(B));for(auto in:B){ while(sz(A) and A.back()>w/in) hh.PB(0),A.pop_back();hh.PB(1); }
for(auto in:A) hh.PB(0);reverse(all(hh));
ll ans=1;for(int i=0,now=1;i<n;i++) (ans*=now)%=MOD,now+=(hh[i]?-1:1);write(ans);

在考虑一般情况。注意到w是非负数,一正一负一定合法,所以可以对正、负各自独立处理出一个顺序

那么我们需要求出$f_i,g_i$分别表示正、负分成i段的方案数,然后用类似$C_{(i)+(i+1)}^i f_ig_{i+1}$求答案

恰i段不好求,但至多i段很好求,将之前空位的初始值从1改成i即可。最后容斥回去,$f_i=\sum_{j=0}^{i} (-1)^{i-j}f‘_j$

求这个暴力求就是$O(n^2)$,顺带一提,分治NTT+多点插值可以优化到$O(nlog^2)$,容斥部分就是一次卷积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void work(vc<int> &hh,ll f[])
{
vc<int> A,B;for(auto num:hh) if(1ll*num*num<=W) A.PB(num); else B.PB(num);hh.clear();
sort(all(A)),sort(all(B));for(auto in:B){ while(sz(A) and A.back()>W/in) hh.PB(0),A.pop_back();hh.PB(1); }
for(auto in:A) hh.PB(0);reverse(all(hh));
fo(st,0,sz(hh)){ tmp[st]=1;int now=st;for(auto in:hh) (tmp[st]*=now)%=MOD,now+=(in?-1:1); }
fo(i,0,sz(hh)) fo(j,0,i) add(f[i], tmp[j]*C(i,j)%MOD*((i-j)&1?MOD-1:1)%MOD );
}
void main()
{
int n=qread();W=qread();vc<int> pos,neg;fo(i,1,n){ int x=qread();if(x>=0)pos.PB(x);else neg.PB(-x); }
PRE();work(pos,f),work(neg,g);
ll ans=0;fo(i,0,n) add(ans, (f[i]*g[i]*2+f[i]*g[i+1]+f[i+1]*g[i])%MOD );write(ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/48296601.html
转载请注明出处,谢谢!