「置顶」6月做题记录

6月做题记录
最后一个6月份了,年份都不用写了;即使实力不强也希望这份题单能给后人一些帮助

Rose的数论题

题意:给定模数P=$n个不同质因数p_i$的乘积,给出pi,对于给定的m,输出$\sum_{x=0}^{P-1} [x^m=x \pmod P]$,$n \le 1e5,p_i,m \le 1e18$

请先思考后再展开

先考虑$n=1$:

rose告诉我可以打表,然后打了半天啥也没看出来,理性分析一下发现不难,可能打表水平是真的低(xld表示难以置信)

需要掌握模意义的阶、原根相关知识;为了下文方便,忽略x=0的情况即当做是$x^{m-1}=1 \pmod P$,最后+1即可

即原根为g,$将x表示为g^i$,$对于j \in [0,p-2],ans_{j+1}=\sum_{i=0}^{p-2} [g^{ij}=1]$

考虑到$阶(g)=p-1$,$阶(g^j)=最快多少步能到p-1=lcm(j,p-1)/j$

根据阶的性质,$阶(g^j)|i$,即$ans_{j+1}=\frac{p-1}{阶(g^j)}=gcd(j,p-1)$,因此可能可以打表发现


那么对于$n>1$:也不难啊,居然没想到qwq……

还是先不考虑x=0,还是写成$x^{m-1}=x \pmod P$,变形一下,$x^{m-1}-1=0 \pmod P$

显然有$\forall i,(x^m-1) \%p_i=0$这个必要条件,而根据中国剩余定理这是充分的

在每个子问题中可行的解(不含0)中选一个,构成n条同余方程,中国剩余定理告诉我们在模P意义下恰一个解,且非0

因此最后答案为,$1+\prod_{i=1}^n gcd(m-1,p_i-1)$


另外,rose从zjt处得知,借助抽象代数知识,可以做质因子次幂不为1的情况

「XR-4」混乱度

请先思考后再展开

显然有$f(l,r)=f(l,r-1)*C(\sum_{i=l}^{r} a_i,a_r)$,因此每个f是个组合数连乘

考虑枚举每个左端点,右端点递增地去维护组合数的连乘

根据Lucas定理,$C_{n+m}^n \%p$,若n+m在p进制下进位了,则为0,因此每个左端点最多会发生$p*log_pa$次某个数位的变化,

特判掉ai=0的情况(组合数不会变,乘上区间长度即可),则每个右端点都会造成至少一次变化

将每个a分解到p进制下,只需要统计非0位,就能统计出组合数

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
int c[10][10];int nxt[N];
vc<int> a[N],pos[N];
void main()
{
int n=qread(),p=qread();
fo(i,1,n)
{
ll num=qread();
while(num){ int x=num%p;num/=p;if(x)pos[i].PB(sz(a[i]));a[i].PB(x); }
}
nxt[n+1]=n+1;fd(i,n,1) nxt[i]=(!sz(pos[i])?nxt[i+1]:i);
c[0][0]=1;fo(i,1,p){ c[i][0]=1;fo(j,0,i) c[i][j]=(c[i-1][j-1]+c[i-1][j])%p; }
ll ans=0;
fo(l,1,n)
{
ll now=1;vc<int> s(100);
fo(r,l,n)
{
ans+=(nxt[r]-r)*now,r=nxt[r];if(r>n) break;
ll sum=1;
for(auto i:pos[r]) {
s[i]+=a[r][i];if(s[i]>=p)sum=0;
sum=sum*c[s[i]][a[r][i]]%p;
}
if(!sum) break;now=now*sum%p;ans+=now;
}
} write(ans);
}

「noiac省选模拟赛2020 R5」function

题意:先给定平面上n个点,q次询问一个矩形,分别求出矩形内,不同的x、y坐标;强制在线,$n,q \le 1e5$,空间1024M,4s

请先思考后再展开

原题是$n=1e5$,分块+bitset就好了,常数挺小,$O(n(n+q)/32)$

对每个x考虑其内的y,那么可以拆成$(y_{i}+1,y_{i})-(y_i,\infty)$这样的矩形

等价于对每个$x \in [xl,xr]$,询问点$(yl,yr)$在多少个矩形内

将矩形二维差分下,问题就变成了三维数点,点数为n,询问次数为n,可以做到$O(nlog^2)$,虽然空间也要这么多

顺便科普下,点给定,权值满足可差分性,强制在线三维数点怎么$O(nlog^2)$做:

对x排序,可持久化线段树套线段树当然是可以的,而且不要求可加性,但是空间常数会上天,不太可行

考虑怎么把一层线段树换成树状数组,那肯定是换外层的更灵活好写

那问题就在于怎么把树状数组可持久化。我们知道每次只会更改log个位置的线段树树根,那么我们对于每个位置,记录他在哪些时间(x)发生了改变,需要时二分找到正确的树根即可

核心代码:

1
2
3
4
5
6
7
8
9
int time;//排序后,当前第一维
int rt[N];//树状数组,维护线段树的根
vc<pii> root[N];//第二维的第i个位置的根,在哪些第一维变成了什么,空间复杂度为nlogn
#define lowbit(x) ((x)&-(x))
void insert(int y,int z,int val){for(int now=y;now<N;now+=lowbit(now)) sgt_add(z,val,rt[now]),root[now].PB({time,rt[now]}); }
int ask(int x,int y,int zl,int zr){int ret=0;for(int now=y;now;now-=lowbit(now))
ret=ret+sgt_ask(zl,zr, (*--upper_bound(all(root[now]),pii{x,INF})).SE );return ret; }
int ask(int xl,int xr,int yl,int yr,int zl,int zr){
return (ask(xr,yr,zl,zr)-ask(xr,yl-1,zl,zr))-(ask(xl-1,yr,zl,zr)-ask(xl-1,yl-1,zl,zr)); }

完整代码

「牛客IOI周赛17-提高组」三角形和线段

题意:保证没有三点共线,求选出一个三角形和线段的方案数,使得没有交点,$n \le 300$,都是整点

请先思考后再展开

枚举线段AB,将平面划分成两半,两侧内部的$C(x,3)$肯定是没有交点的,以左边选1个,右边选两个点为例

枚举左边z,连向A、B,则在右侧且在A下面,或者B上面,分别有q和w个点,则方案数为$C_q^2+C_w^2+qw$

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
V pt[N];vc<int> sot[N];//对每个点为中心做极角排序
int cnt[N],L[N],R[N];
void main()
{
int n=qread();fo(i,1,n) pt[i].x=qread(),pt[i].y=qread();
fo(st,1,n)
{
int mid=st%n+1;vc<int> L,R;
fo(i,1,n) if(i!=st and i!=mid) (pt[st].cross(pt[mid],pt[i])>0?L:R).PB(i);
sort(all(L),[&](int a,int b){ return pt[st].cross(pt[a],pt[b])>0; });
sort(all(R),[&](int a,int b){ return pt[st].cross(pt[a],pt[b])>0; });
for(auto x:R) sot[st].PB(x);sot[st].PB(mid);for(auto x:L) sot[st].PB(x);
}
ll ans=0;
fo(A,1,n) fo(B,1,n) if(A!=B)//(A->B)左边选1右边选2
{
int stl,str,sl,sr;fo(x,1,n) cnt[x]=0;
sl=sr=0;for(auto x:sot[A]) if(x!=B) pt[A].cross(pt[B],pt[x])>0?L[sl++]=x:R[sr++]=x;
if(A<B) ans+=sl*(sl-1)*(sl-2)/6+sr*(sr-1)*(sr-2)/6;//两侧独立选 C(x,3)
if(!sl or !sr) continue;
stl=0;fo(t,1,sl-1) if(pt[A].cross(pt[L[t]],pt[L[stl]])>0) stl=t;
str=0;fo(t,1,sr-1) if(pt[A].cross(pt[R[t]],pt[R[str]])>0) str=t;//对A逆时针
for(int i=stl,j=str,i2=stl,j2=str;i<stl+sl;i++,i2++)
{
if(i2==sl) i2=0;
while(j<str+sr and pt[L[i2]].cross(pt[R[j2]],pt[A])>0){ j++,j2++;if(j2==sr) j2=0; }
cnt[L[i2]]=j-str;
}
sl=sr=0;for(auto x:sot[B]) if(x!=A) pt[A].cross(pt[B],pt[x])>0?L[sl++]=x:R[sr++]=x;//点集不变,内部顺序变
reverse(L,L+sl),reverse(R,R+sr);
stl=0;fo(t,1,sl-1) if(pt[B].cross(pt[L[t]],pt[L[stl]])<0) stl=t;
str=0;fo(t,1,sr-1) if(pt[B].cross(pt[R[t]],pt[R[str]])<0) str=t;//对B顺时针
for(int i=stl,j=str,i2=stl,j2=str;i<stl+sl;i++,i2++)
{
if(i2==sl) i2=0;
while(j<str+sr and pt[L[i2]].cross(pt[R[j2]],pt[B])<0){ j++,j2++;if(j2==sr) j2=0; }
int x=cnt[L[i2]],y=j-str;
ans+=x*(x-1)/2+y*(y-1)/2+x*y;
}
} write(ans);
}

「BJOI2018」双人猜数游戏

请先思考后再展开

起因是看到这篇文章,感觉非常帅,结果被xgc告知在省选中出现过……

题答应该是为了允许手玩降低难度吧

再次莫名其妙搞了一上午,做法可能和网上题解本质上是一样的,只是实现区别非常大(感觉可能建图方式都不同,我的点是和或乘积,正常人则是$(m,n)$作为点

思路应该大家都差不多的,并不复杂,而且可以玩样例得到思路


考虑一个上界N表示我们只考虑N以内的数求答案,写完再调整具体大小(我开了3e5)

令图上有2N个点,分为和点、积点。对于那些和点x,想作为叶子(定义为deg=1的点)的话,需要满足$x=2s或2s+1$,此时一定是连向一个叶子积点,而题目中$t \ge2$保证我们无需考虑这种情况

(这步转化没有也行)那么只需考虑那些叶子积点,此时如果先问Bob是没有任何意义的,所以可以跳过问他,直接从Alice开始(t–)

如果Alice说不知道,则Alice必定不是叶子积点,所以把所有叶子积点删除,进入下一轮

如果Bob说不知道,则Bob必定不是此时的叶子和点,所以把此时的所有叶子和点删除,进入下一轮
……

如果此时说知道,则此时的叶子点x,可以作为答案的条件是,唯一连出去的另一个点y,可以作为另一个人的答案

这个的限制条件是,在第t+1轮,y点周围,只有x这一个点,是刚被删除的


因此,可以做个类似拓扑的过程,因为有较多限制,访问到的点不会很多,枚举每条边就能在1s内通过每个测试点(luogu似乎就是这样测的)

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
int hav[2][N];
int real[2][N];//用于判断,周围第r次时才知道,自己是正确的,节点个数
int deg[N];vc<int> dd[N];//都是用来判断度数的
bool del[N][2];
void main()
{
int s=qread();char name[10];scanf("%s",name);
int t=qread()+1;if(name[0]=='B') t--;//保证A先手
fo(num,s+s,N-1) deg[num]=(num/2)-s+1;
fo(i,s,sqrt(N)) for(int j=i*i;j<N;j+=i) dd[j].PB(i);
queue<pii> q;fo(num,1,N-1) if(sz(dd[num])==1) q.push({num,1}),del[num][1]=1;
vc<pii> ans;
fo(tim,1,t)
{
ass(sz(q));vc<pii> chk;
while(sz(q))
{
int x=q.front().FR,op=q.front().SE;q.pop();
if(op==0)//和
fo(y,s,x/2)
{
int m=y,n=x-y;if(1ll*n*m>=N or del[n*m][1])continue;hav[1][n*m]++;
if(tim==t) real[1][n*m]++;
if(tim==t or hav[1][n*m]+1==sz(dd[n*m])) chk.PB(pii{m,n});
}
else//积
fo(y,s,sqrt(x)) if(x%y==0)
{
int m=y,n=x/y;if(n+m>=N or del[n+m][0])continue;hav[0][n+m]++;
if(tim==t) real[0][n+m]++;
if(tim==t or hav[0][n+m]+1==deg[n+m]) chk.PB(pii{m,n});
}
}
for(auto in:chk)//in=(m,n)
{
int s=in.FR+in.SE;
if(tim&1)
{
if(tim==t){ if(real[0][s]==1 and real[0][s]<deg[s]) ans.PB({s,in.FR}); }
else if(hav[0][s]+1==deg[s] and !del[s][0]) q.push({s,0}),del[s][0]=1;
}
else
{
int mu=in.FR*in.SE;
if(tim==t){ if(real[1][mu]==1 and real[1][mu]<sz(dd[mu])) ans.PB({s,in.FR}); }
else if(hav[1][mu]+1==sz(dd[mu]) and !del[mu][1]) q.push({mu,1}),del[mu][1]=1;
}
}//检验合法性,并放入堆中
}
ass(sz(ans));pii out={INF,INF};for(auto in:ans) chmin(out,in);
write1(out.SE),write(out.FR-out.SE);
}

「Hdu4609」3-idiots

请先思考后再展开

当年学FFT的例题,差点不会做

考虑有A个合法方案,B个非法方案,$A+B=C_n^3$

注意到$i+j>k$这个条件,在A中会被统计3次,在B中会被统计两次,因此$3A+2B$是易求的

FFT优化即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lg=18,m=bin(lg);
fo(T,1,qread())
{
mem(cnt,0),mem(hh,0);
int n=qread();fo(i,1,n) cnt[qread()]++;
fo(i,0,m-1) A[i]=FFT::Cp(cnt[i],0);FFT::DFT(A,lg);
fo(i,0,m-1) A[i]=A[i]*A[i];FFT::DFT(A,lg,1);
fo(i,0,m-1) hh[i]=round(A[i].r/m);
fo(i,0,m-1) if(i*2<m) hh[i*2]-=cnt[i];
fo(i,0,m-1) assert(hh[i]%2==0),hh[i]/=2;
ll nn=1ll*n*(n-1)*(n-2)/6;
ll sum=0,ans=0;fo(i,0,m-1) ans+=hh[i]*(sum-2),sum+=cnt[i];
ans=nn-(3*nn-ans);printf("%.7lf\n", 1.0*ans/nn );
}

「HEOI2016/TJOI2016」字符串

请先思考后再展开

复习,顺便更新下当时的题解

一开始看错题以为是求和,感觉不太可做啊

二分答案L,问题转化成,后缀排序后,区间中是否有$[a,b]$间元素i,且$b-i+1 \ge L即i \le b-L+1$,主席树,$O(nlog^2)$,code

1
2
3
4
5
6
7
8
9
10
11
12
13
int n=qread(),m=qread();scanf("%s",SA::str+1);SA::build();
fo(i,1,n) rt[i]=rt[i-1],CMT::insert(SA::sa[i],rt[i]);
while(m--)
{
int a=qread(),b=qread(),c=qread(),d=qread(),g=SA::rk[c],MX=0;
for(int fl=1,fr=d-c+1;fl<=fr;)
{
int L=(fl+fr)/2;
int gl=g;for(int tl=1,tr=g-1;tl<=tr;){ int mid=(tl+tr)/2;if(SA::ask(mid+1,g)>=L) gl=mid,tr=mid-1; else tl=mid+1; }
int gr=g;for(int tl=g+1,tr=n;tl<=tr;){ int mid=(tl+tr)/2;if(SA::ask(g+1,mid)>=L) gr=mid,tl=mid+1; else tr=mid-1; }
if( CMT::ask(a,min(b,b-L+1),rt[gl-1],rt[gr])>0) MX=L,fl=L+1; else fr=L-1;
} write2(MX);
}

还有一个sam的做法,先翻转变为求后缀,然后网上的线段树合并需要新建节点,这里给出一个和普通线段树合并没区别的做法:在外层枚举这是第几次二分,然后把目前依然没有得出答案的人倍增挂到parent树上,然后线段树合并求right集合,时间复杂度为 $O(n log^2 n)$

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