二次剩余

ACdreamers 二次同余方程的解

方程有解当且仅当\(a^{\frac{p-1}{2}}\equiv 1( \% p)\)。
。。。还是看ACdreamer博客吧

51nod 1014
虽然暴力也能过。。。

原根

定义:
设\(m\)是正整数,\(a\)是整数,若\(a\)模\(m\)的阶等于\(\phi(m)\),则称\(a\)为模\(m\)的一个原根。

51nod 1135
求原根。
最小原根求法:
对\(p-1\)分解,从小枚举\(g\)。若\(g^{\frac{p-1}{primeFactor_i}}\)恒成立,则\(g\)为原根。

BSGS算法

BSGS算法
poj 2417
问题描述:
给定\(B\)、\(P\)、\(N\)。求使\(B^L \equiv N ( \% \ P)\)的最小\(L\)解。

首先,判断\(B\)和\(P\)互质,否则无解。
设\(x=im-j\),\(m=\left \lceil \sqrt{m} \right \rceil\)。那么问题可以化解成:\((a^m)^i \equiv ba^j ( \% P)\)。
只需要枚举\(i\),\(j\)即可。
先枚举\(j\in [0,m]\),记录\(ba^j\)和对应的最大的\(j\)。
枚举\(i\in [1,m]\),查询\((a^m)^i\)对应是否有,返回答案。

Codeforces Round #433

💀D没交上去哇。
A. Fraction

B. Maxim Buys an Apartment
n个格子,放k个东西,最多多少格子跟这K个相邻。
\(ans=min(k*2,n-k)\)。特判边界。

C. Planning
贪心,选取当前区间耗费最大的。

D. Jury Meeting
n+1个城市,0~n,0是中心。要求将其余n个城市的人集中起来至少k天同时在一起。
题目给出m个航班的出发地和终点信息和时间以及耗费。
要求最小耗费。
考虑以时间为横轴,l[x]保存的是第x天所有人能够到达0的最低消费。
可以对每个城市维护dayx之前消费的最小值。统计和可以更新。
同理对于r[]统计处后缀和。
为什么有人说40行就写好了?🙄

Codeforces Round #432 (Div. 2)

👹👺😭不知道为什么pp特别容易过。瞎交防fst其实没必要。D读错题意,却锁题hack。。。

A. Arpa and a research in Mexican wave
判断输出就行。

B. Arpa and an exam about geometry
先判断是否共线,然后判断是否距离相等。

C. Five Dimensional Points
暴力判断就好了,怕fst判断\(3^5\)以上必定没有。

D. Arpa and a list of numbers
枚举gcd,然后选取区间计算贡献。
通过x,y计算出是的删去和加分别最优的点。
[l,t-1]是删去,
[t,r]是加。
因为傻逼读错题而特盼了不为空,以及没处理好r端点导致fst…。

莫比乌斯反演

源自[kuangbin]莫比乌斯反演.
A – Visible Lattice Points[SPOJ VLATTICE]
简化为:求满足\(gcd(x,y,z)=1\)的个数。
设\(F(d)\)表示约数为\(d\)的个数。\(F(d)=\left \lfloor {\frac{n}{d}} \right \rfloor^3 + 3\left \lfloor {\frac{n}{d}} \right \rfloor^2\)。
\(F(n)=\sum_{d|n}f(d)\Leftrightarrow f(d)=\sum_{d|n} \mu(\frac{n}{d})F(d)\)枚举\(n\),考虑到有一些段\(n/i=n/(i+1)\),可以利用分块+mu函数前缀和计算。
最后答案要加上(0,0,1),(0,1,0),(1,0,0).

B – GCD
求\(gcd(x,y)=k\)的对数。
相当于求\(x\in [1,\left \lfloor \frac{n}{k} \right \rfloor]\),\(y\in [1,\left \lfloor \frac{m}{k} \right \rfloor]\)中满足
\(gcd(x,y)=1\)的对数。
\(F(d)=F(d)=\left \lfloor \frac{n}{d} \right \rfloor \left \lfloor \frac{m}{d} \right \rfloor\)。
那么\(f(d)=\sum_{d|n}\mu(\frac{n}{d})F(d)\)枚举n。删去\(x=y\)的个数的一半。

C – Mophues
设\(d(i)\)为i的质因子个数,那么求\(d(gcd(i,j))\leq P\)的对数。
因为\(2^{19} > 500000\),所以预处理到18就够了。
于是,求个j<=i&&p<=k的前缀和就行了。 计算时仍然利用分块计算。

D – GCD of Sequence
给定一个长度为n的序列a,且\(1\leq a[i]\leq m\),求有多少个序列b,使得\(gcd(b[1],b[2],…b[n])=d|(1\leq d\leq m)\),且正好有k个b[i]!=a[i]。
有\(f(n)=\sum_{d|n}^{}\mu(\frac{n}{d})F(d)\)。
设\(tot\)指那些为\(d\)倍数的数字的个数。
如果\(n-tot > k\),那么无论如何会有数字不是\(d\)的倍数。
只有\(n-tot \leq k\)时,首先这n-tot个数要换成\(d\)的倍数,各\(\left \lfloor \frac{m}{d} \right \rfloor\)种。然后剩下的tot个数里选择k-(n-tot)个数字换成不等于他们自己的d的倍数,各\(\left \lfloor \frac{m}{d}-1 \right \rfloor\)种。
所以\(F(d)=\left \lfloor \frac{m}{d} \right \rfloor ^ {tot-n} \left \lfloor \frac{m}{d}-1 \right \rfloor ^ {k-(n-tot)}\textrm{C}_{tot}^{k-(n-tot)}\)。

E – Gcd
枚举素数,求gcd(x,y)=k的答案,乘以2,减去均为素数的。

F – 能量采集
连线上有k个,贡献为2k+1。\(ans=\sum_{i=1}^{n}\sum_{j=1}^{m}2gcd(i,j)-1\)。
即求\(\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)\).
欧拉函数 莫比乌斯函数都能A。

G – Problem b
加个容斥原理,分块求和。

bzoj 2820
bzoj 2820
枚举质数处理前缀和。

AtCoder Regular Contest 082

题目链接:http://arc082.contest.atcoder.jp/

C – Together
N个数字,每个数字可以进行加1,减1,不变三种操作,确定一个数字X,使得一次操作后变成X的数最多,并输出数量。

D – Derangement
序列p是1~n的一种排列,每次操作可以使得相邻两个数交换位置,为了使得pi != i,问最少操作几次。
若相邻的两个数字都满足pi == i,则这两个数只需相互对调一次,其他每个数字若不满足条件则交换一次。

E – ConvexScore
给出N个点,这N个点可以形成若干个子集S,每个S满足如下条件:S里的所有点正好形成一个凸多边形,每个点都是凸多边形的顶点。
对于任意一个S,n是N个点散布在S的凸包内的个数(包括边界和顶点),S相对应的得分为\(2^{n-|s|}\)。求所有得分和,结果模998244353。

令Ts = n – |S|,Ts即为集合S的凸包内的点组成的集合(除顶点以外),则题目要求的是合法的Ts子集的种数,Ts最多为\(2^n\),然后减去不合格的集合个数。首先,减去一个空集,再减去n个单点集,然后减去共线的情况(集合全在一条线段上)。

F – Sandglass
给一个沙漏,一半叫A,另一边叫B,初始A在上B在下,A+B的沙子一共为X,每秒钟走一滴沙,再给出k个时刻,每个时刻都将沙漏倒置,现在有Q个询问,每个询问(t,a)代表若起始A中有a滴沙,t时刻时A中还有多少沙子,每个询问的时刻t是递增的给出。

ft(x)表示若A中初始沙数量为x,在t时刻A中剩余的沙的数量。举几个例子之后会发现,ft(x)的函数都是这样的

(x前面的斜率也可以为-1),同时函数上限不会超过X,下限不会低于0,模拟即可

2017ACM/ICPC广西邀请赛-重现赛

1001 A Math Problem
枚举\(k^k\),\(k \leq 15\)。

1002 Color it
线段树,按y排,存x坐标,维护min
按x排存y坐标也行的,
防止炸空间,可以离散化或者像我这样,用到哪建到哪,最多是nlogn的.

1003 Counting Stars
统计有多少\(V=(A,B,C,D)\),\(E=(AB,BC,CD,DA,AC)\)。
考虑一个边作为对角线时,如果有K个点跟这个边的两个端点都相连,那么有\(\textrm{C}_{K}^{2}\)中方案。
统计时,让边记录在度数比较少的点处,减少枚举次数,每次将3个边一起算贡献。

1004 Covering

Number of domino tilings of 4 X (n-1) board.

\(a_n = a_{n-1} + 5a{n-2} + a_{n-3} – a_{n-4}\),直接用杜教板子。。

1005 CS Course
求三种sum丢掉第k位
预处理出所有的前缀和后缀
黑康说:按位枚举???emmm

1006 Destroy Walls
国王的坐标给的那么恶心的数字,就是告诉你,国王不会在wall上,然后要让国王能到达任意地方,就要让这些wall无法形成环就可以了,所以,不是环,树嘛,要求删去的最少,求个最大生成树,然后\(ans = sum_{all} – sum_{tree}\)。

1007 Duizi and Shunzi
贪心:取i,i-1,i-2这个顺子的时候先把i-1,i-2的对子取掉,取完再取i的对子。

1008 Law of Commutation
开始打表的时候发现如果a是奇数的时候肯定是1。
然后a是偶数的时候,2的因子个数很多,枚举一下就行了,后面的就为0了。
开始打表发现,\(a \geq n\)的时候,几乎是所有的偶数,无脑了几发。发现\(a \leq n-1\)的时候答案不对。事实上,枚举一下较小的部分。加上后面0的部分。

1010 Query on A Tree
[BZOJ3261 最大异或和]
首先,如果是区间异或的话,可以用可持续化Trie树。对于树上的可以用dfs序做。查询就查询in[u]到out[u]的的区间就行了。

矩阵优化

51nod 1033
因为行数比较少,\(n\leq 5\)。我们用二进制表示当前状态,比如说\(10101\)表示第1,3,5行放了,第2,4没放。用数组\(a[i][j]\)表示状态\(i\)到状态\(j\)的方案数。最终求的是第\(0\)层\(0\)到第\(m\)层\(\underset{m}{1111…1}\)状态的方案数,相当于矩阵\(a^{n+1}\)。

2017 Multi-University Training Contest – Team 10

1001 Admiral
给一个样例样式的图形,每次只能移动0,与上下四个交换,问最少能到达目标的次数。
最多20步,每步大约4个状态,大约需要\(4^{20}\)的复杂度,爆炸。
考虑双向宽搜,每次只需要搜一半。\(4^{10}+T*4^{10}\)可以接受。