Believe it

相信不屈不挠的努力,相信战胜死亡的年轻

题目1

2018宁夏网络赛H题

给你类似剪刀石头布游戏的五种手势和十种克制关系。每种手势克制其他两种手势并被另外两种手势克制。给你两个字符串分别表示A,B的 手势顺序,A长B短,你可以随意挪动B相对于A的位置,求B最多能赢多少次?

1
2
3
4
5
6
7
8
9
10
11
若两个串为abcde和ede
则共有三种方法来决斗,
abcde
eda

abcde
eda

abcde
eda
为每一个字符标上指数,将一个串逆置后,发现是fft

题目2

BZOJ4259

给你两个字符串原串和匹配串,串里只包含小写字母和,可以表示任意字符,问匹配串在原串不同位置中出现多少次,起始位置不同即不同位置。 我们还是利用上一题逆置短串构造卷积的方法,我们把*的值当作赋为0,pow(str1[i]−str2[i],2)*str1[i]*str2[i]化简消去负数项即可

FFT

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
const int maxn=4e6//开四倍所有数组。准确的数值是乘法结果数组的2进制对齐那么大。这个值小于四倍,
const double pi=acos(-1.0);

struct cp{
double x,y;
cp(double X=0,double Y=0){x=X,y=Y;}
cp operator + (cp b){return cp(x+b.x,y+b.y);}
cp operator - (cp b){return cp(x-b.x,y-b.y);}
cp operator * (cp b){return cp(x*b.x-y*b.y,x*b.y+y*b.x);}
};

// opt = 1 把系数表达式变为点值表达式
// opt =-1 把点值表达式变成系数表达式
// 传参的时候必须要求n为2的bits次方
int r[maxn];
void fft(cp *a,int n,int bits,int opt){
for (int i=0; i<n; ++i){
r[i]=(r[i>>1]>>1)|((i&1)<<(bits-1));
if (i<r[i]) swap(a[i],a[r[i]]);
}
for (int k=1; k<n; k<<=1){
cp wn=cp(cos(pi/k),opt*sin(pi/k));
for (int i=0; i<n; i+=(k<<1)){
cp w=cp(1,0);
for (int j=0; j<k; ++j,w=w*wn){
cp x=a[i+j],y=w*a[i+j+k];
a[i+j]=x+y,a[i+j+k]=x-y;
}
}
}
}

// 没有必要分x和y的长度,没有意义,对时间复杂度影响不大
// 传数组使用闭区间[0,n-1],n-1为多项式最高次数
// xy甚至可以传一个x或y一样的参数 例如mul(f,g,f,n,m)等价于f*=g
cp cpa[maxn],cpb[maxn];//经测试, 两个1e6的多项式乘起来大概的时间700ms,
void mul(int*x,int*y,int*xy,int xn,int yn){
int exn=1,bits=0;
while(exn-1 < xn-1+yn-1)exn<<=1,bits++;//exn为xy数组拓展的长度,bits为lg(exn)
for(int i=0 ;i<xn ;i++)cpa[i]=cp(x[i],0);
for(int i=xn;i<exn;i++)cpa[i]=cp(0,0);//按0补齐
for(int i=0 ;i<yn ;i++)cpb[i]=cp(y[i],0);
for(int i=yn;i<exn;i++)cpb[i]=cp(0,0);//按0补齐
fft(cpa,exn,bits,1);fft(cpb,exn,bits,1);//化为点值表示法
for(int i=0; i<exn;i++)cpa[i]=cpa[i]*cpb[i];//乘
fft(cpa,exn,bits,-1);//化为系数表示法
for(int i=0; i<exn;i++)xy[i]=cpa[i].x/exn+0.5;//赋值结果
}

NTT

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
typedef long long ll;
// ll mod=1004535809,g=3;// 479*pow(2,21)+1
// ll mod=998244353,g=3;// 119*pow(2,23)+1
// ll mod=2281701377,g=3;// 17*pow(2,27)+1

ll qpow(ll a,ll b,ll mod){
ll ret=1;
while(b){
if(b&1) ret=ret*a%mod;
a=a*a%mod;
b>>=1;
}
return ret;
}

const ll maxn=1e6;
ll r[maxn];
void ntt(ll*a,ll n,ll bits,ll opt,ll g,ll mod){
for(ll i=0;i<n;i++) {
r[i]=(r[i>>1]>>1)|((i&1)<<(bits-1));
if(i<r[i]) swap(a[i],a[r[i]]);
}
for(ll k=1;k<n;k<<=1){
ll wn=qpow(g,(mod-1)/(k<<1),mod);//用原根代替单位根
if(opt==-1) wn=qpow(wn,mod-2,mod);//逆变换则乘上逆元
for (ll i=0;i<n;i+=(k<<1)){
for (ll j=0,w=1; j<k; j++,w=w*wn%mod){
ll x=a[i+j], y=w*a[i+j+k]%mod;
a[i+j]=(x+y)%mod, a[i+j+k]=(x-y+mod)%mod;
}
}
}
if(opt==-1) {
ll inv=qpow(n,mod-2,mod);
for(ll i=0;i<n;i++) a[i]=a[i]*inv%mod;
}
}

ll cpx[maxn],cpy[maxn];
void mul(ll*x,ll*y,ll*xy,ll xn,ll yn,ll g,ll mod){
ll exn=1,bits=0;
while(exn-1 < xn-1+yn-1)exn<<=1,bits++;//exn为xy数组拓展的长度,bits为lg(exn)
for(ll i=0 ;i<xn ;i++)cpx[i]=x[i];
for(ll i=xn;i<exn;i++)cpx[i]=0;//按0补齐
for(ll i=0 ;i<yn ;i++)cpy[i]=y[i];
for(ll i=yn;i<exn;i++)cpy[i]=0;//按0补齐
ntt(cpx,exn,bits,1,g,mod); ntt(cpy,exn,bits,1,g,mod);//化为点值表示法
for(ll i=0; i<exn;i++)cpx[i]=cpx[i]*cpy[i]%mod;//乘
ntt(cpx,exn,bits,-1,g,mod);//化为系数表示法
for(ll i=0; i<exn;i++)xy[i]=cpx[i];//赋值结果
}

这是我自己给这类图取的名字

给出定义, 有五类边

  • 第一类为原点到左边的点,容量无穷大,有费用

  • 第二类为左边的点到右边的点,一对一,容量为任意常数,费用0

  • 第三类为右边的点到汇点,容量无穷大,费用0

  • 第四类为左边的点依次连i->i+1,容量无穷大,费用0

  • 第五类从右边连向左边,容量无穷大,费用0

如下图左边的图

给出问题,求当有容量的边的都满流时的最小费用

我们发现左图的最大流一定满足有容量的边是满流的,我们尝试将其转化为最小费用最大流 我们发现,如果我们对左边的图跑最大流,当左边的图有流量进入y点集的时候,他一定会进 入源点,不会流回x点集,这就很烦,我们要的不是最大流,而是指定边的满流,我们尝试“阻 止”这个过程,怎么阻止呢,我们在考虑一个z点集,从源点出发,每当y点集有流量流入汇点,就从源点流等量流量到对应的z点集,我们最后用z点集完全替代y点集的回流功能,这样以后, 最小费用最大流就成了我们要求的最小费用固定流。

再仔细想想,我们发现y点集已经没有作用了,删掉他们,最后成了上图的右边的图。 于是解决了。

对于流入汇点的流量,我们可以构造一个新的点集,每当有流量流入汇点,我们就从源点流入 新的点集,实现回流机制。

为了便于叙述,我们将二分图分为左边的点与右边的点来叙述。我们称二分图匹配成功的边为匹配边,称匹配成功的点为匹配点,二分图匹配数为匹配边的条数。 于是最小顶点数等于二分图匹配数。

先证明最小顶点数大于等于二分图匹配数。从反面考虑,少于二分图匹配数的顶点绝对不可能覆盖二分图,因为这些顶点无法覆盖所有的匹配点。

再证明至少存在一个数量为二分图匹配数的顶点集,可以覆盖二分图。

正面来做,我们先来找这个集合。

我们来对二分图进行染色,从右边任取一个非匹配点开始,我们沿着二分图的边走,遵循这样一种走法:“标记右边未匹配边的顶点,并从右边未匹配边的顶点出发,按照边:未匹配->匹配->未匹配...,的原则标记途中经过的顶点,则最后一条经过的边必定为匹配边。重复上述过程,直到右边不再含有未匹配边的点。”(注意标记就是染色的意思)(注意孤立点没路走,直接染色,不要忽视)(为了让读者深入理解,笔者故意不画图,让读者自己画)

那么左边的染色点加上右边的非染色点便是我们要找的顶点集。

下面证明该集合的点数为匹配数且覆盖二分图。

------------------------------

先证明该集合点数为匹配数:

我们观察所有的匹配边,如果他被走过,说明他是被从左往右走的,那么它的两个端点都被染色;如果他没有被走过,说明已经没有多余的边可以到他的左端点了,那么他的两个端点都没有被染色。也就是说对于所有的匹配边,要么两个端点都被染色,要么两个端点都未被染色。

现在我们可以断言,如果左边的染色点集是左边的匹配点集的子集且右边的非染色点集是右边的匹配点集的子集,那么染色点个数等于匹配数。这里不好描述,但好证明,笔者不证明了。

下面来证明上诉前提条件是恒成立的。

右边的非染色点集是右边的匹配点集的子集,可以用反证:如果存在一个右边非染色点不属于右边的匹配点集,那么这个点肯定是非匹配点,这与我们的染色规则矛盾。

左边的染色点集是左边的匹配点集的子集,我们依旧反证:如果存在一个左边的点不属于左边的匹配点集,那么说明有一个右边的非匹配点可以走到当前的非匹配点,这与二分图最大匹配矛盾。

------------------------------

再证明该点集覆盖二分图:

我们考虑边,分三种

  • 右端点为非染色点,这些边被右边的非染色点集覆盖
  • 右端点为染色点,左端点为染色点,这些边被左边的染色点集覆盖
  • 右端点为染色点,左端点为非染色点,都在说这样的边不存在,然而证明过程却给得极其含糊不清。

二分图的构造就讲的含糊不清,为了让读者感到区别,我故意在上面的叙述中引用了带有歧义的染色规则。

因为上述叙述至少有一个反例: img

这个叙述应该改为从右边的非匹配点出发,走二分图,每次从右往左走都走非匹配边,每次从左往右走都走匹配边,(注意这里并没有说走过的点不能再走一次,也没有说起点只有一个)直到无路可走或走入循环,染色所有经过的点和边,重复此操作,直到不能再次染色为止。

依据现在的走法,上图反例不复存在,可以得出正确覆盖。对走法进行影响未改变上文所有证明,下面来证明新走法不存在右端点为染色点,左端点为非染色点的边,这就很明显了,这种边在我们新的走法里面是不存在的,因为可以走这样的边,并染色。

------------------------------

综合得到二分图最小顶点覆盖数等于二分图匹配数。

第一题

P2756 飞行员配对方案问题

求二分图匹配,输出谁和谁匹配

使用反向边是否存在流量来输出路径。

第二题

P2762 太空飞行计划问题

求有向图的最大权闭合子图

将正权点连接s,容量为点权,负权点连接t容量为点权绝对值,所求得的一个割将图分为两部分,我们发现所有正点权的和减去该简单割,便是与s相连的闭合图的权,因为最小割所以最大权闭合图(即给定常数c,求c-a的最大值,等价于求c减去a的最小值)。注意跑完最大流以后,与s相连的点构成的点集就是最大权闭合图。学会了使用bfs之后 的lv数组来输出路径

第三题

P2764 最小路径覆盖问题

求DAG的最小路径覆盖

用原图建立一个两层的新图,如果原图中存在边i->j我 们建立的新图就有第一层的点i流到第二层的点j,最后建立超级源点流向 所有的第一层图的点,建立超级汇点,由所有第二层的图流入,用DAG的总点数减去去所求的最大流就是最小路径。

在构造的二分图中的最大流映射回原图,发现每个点最多有一个入度,一个出度,显然整个图形成了一些不相交的链,于是点数减去边数就是联通块的个数。即总点数减去匹配数就是最小路径数。

第四题

P2765 魔术球问题

依旧是是一个最小路径覆盖的问题,我们考虑把球当作点,把盒子当成路径,那么很明显,连边方式就是i->j当且仅当i<=n且j<=n且i+j=k^2. 但是这样子做我们只能解决这样一个问题: 给你从1到n的n个球我们可以找到最少的盒子来装球。

仔细分析发现题目给的问题可以二分处理,我们二分来判断n个盒子能不能装到k个球就可以了。

第五题

P3254 圆桌问题

给m组人,每个人要分到不同的桌子上,每个桌子可以一定量的人,组内的人不能坐在一个桌子上, 网络流问题,s连到组,流量组内人数,桌子连到t,流量为可以坐下的人数,组与桌子自由组合, 流量为1。

第六题

P2766 最长不下降子序列问题

让你求一个数列的最长不下降子序列的长度k

然后求这个序列最多可以分出多少个长度为k的子序列,

再求如果可以多次使用第一个元素和最后一个元素,可以分出多少个长度为k的子序列

我们考虑到每个元素dp的值(dp[i]表示以i结尾的最长不下降子序列的长度),并以dp值为标准,给所有点分层,并给所有第一层的点连s,所有最后一层的点连t, 如果i<j且a[i]<=a[j]我们就连一条边i->j,如此如果每当从s流到t,就是一个子串,考虑到一个点只能用一次,拆点限流就可以了。

第七题

P2763 试题库问题

给你一个试题库,告诉你每个题目的类型(一个题目可能属于多种类型),让你 用这些题为每个类型组一套题(告诉了你每套题包含的题数),每道题只能用一次, 类型在左,题目在右,s连类型,流量为该套题的题数,类型连题目流量1,题目连 t流量1,如果最大流不够要求的题目数量,说明无法组成套题。

第八题

P2775 机器人路径规划问题

什么怪东西,明明是深搜题

第九题

P2774 方格取数

有一个 m 行 n 列的方格图,每个方格中都有一个正整数。现要从方格中取数,使任意两个数所在方格没有公共边,且取出的数的总和最大,请求出最大的和。

对于格子我们令k=行数加列数,

对于所有的k&1==1内部,无边,

对于所有的k&1==0内部,无边。

于是取走元素就成了:

拿走点,使得这些点覆盖所有边,于是剩下的点就是独立的了, 没有边互相连。就是我们要的答案,所以就成了 最小点覆盖二分图

第十题

P1251 餐巾纸计划

此处不方便证明,详情见: 建图与证明

第十一题

P2770 航空路线问题

给你一个城市数组,这些城市从左往右分别对应从东到西, 要求你从最西边的城市出发,到达最东边的城市,在从最东边的城市出发,到达最西边的城市 除了最西边和最东边的城市以外,其他城市只能经过一次 让你求最多经过多少城市,

考虑最大流,s连最西边的城市,最东边的的城市连t,容量2,对于他给的边只连从东到西的边, 对于一个城市只经过一次考虑拆点限流即可。

想必大家都知道的组合数在正整数上有: \[ C_{a}^{b}=\frac{a!}{b!(a-b)!} \]

但很少有人知道这个公式在实数领域上也是成立的:

也就是说\(n!\)在实数上有定义

\(x!=\gamma(x+1)...\gamma(x)\)为伽马函数

下面问题转移到伽马函数上面了,但是在这里我们所用到的伽马函数的性质只有这一条

\(\gamma(x)=(x-1)\gamma(x-1)\)

为什么这样说呢,因为我们不需要计算\(x!\),我们要算的是这个式子

\[ C_{a}^{b}=\frac{a!}{b!(a-b)!}=\frac{\gamma (a+1)}{\gamma (b+1)\gamma(a-b+1)} \]

下面给出几个简单的我们来算一下 \[ C_{4.5}^{3} =\frac{4.5!}{3!*1.5!} =\frac{\gamma (5.5)}{3!\gamma (2.5)} =\frac{1}{3!}\frac{\gamma (5.5)}{\gamma(2.5)} =\frac{1}{3!}*4.5*3.5*2.5 \]

\[ C_{3}^{4} =\frac{3!}{4!(-1)!} \]

为什么我不继续化简了呢?

如果你是一个思维严谨的读者,当你看到了我放入的伽马函数图像的时候,你就应该对我的博客提出质疑,

我曾经说n!在整个实数领域有意义,又说\(x!=\gamma(x+1)\) ,然而我给出的伽马函数的定义域明显不包含负整数和0,

我一定有一个地方错了。

对的,负数没有阶乘!

我重新给出定义域: \[ C_{a}^{b}=\frac{a!}{b!(a-b)!} \] \(x!\)有意义当且仅当\(x\geq 0||-x\notin Z\)

不管读者如何想,至少我自己认为,如果给要给负数定义一个阶乘的值,依据伽马函数在对应的点的极限为∞,

那么负数的阶乘应该是∞,代入刚刚的式子并化简有 \[ C_{3}^{4} =\frac{3!}{4!(-1)!}=\frac{1}{4}*\frac{1}{infinity}=0 \]

我又写了一个不严谨的证明。。。。。。如果读者有兴趣,自己试着证明一下吧,至少我好像证出来了。

然后继续下一题 \[ C_{-1}^{3}=\frac{(-1)!}{3!*(-4)!} \]

\[ C_{-1}^{-4}=\frac{(-1)!}{(-4)!*3!} \]

哈哈哈哈你说怎么办呢?????

除非无穷大有大小关系,否则这里无法解释,,,,此路不通

数学总是这样,如果我非得让这个式子可以运算,将对很多其他数学定理有很大的影响,而不是那些数学家们不愿意在数学界给出新的运算。给出新的运算就得付出代价。

数学界用这样一种方法来回避这样的问题,重新定义组合数,而不是引入新的运算。

重新定义广义组合数的值 \[ C_{x}^{n}=\frac{\prod _{i=x-n+1}^{x}i}{n!}(x\in R,n\in Z^{*}) \]

如此我们把题目都重新做一遍 \[ C_{4.5}^{3}=\frac{\prod _{i=4.5-3+1}^{4.5}i}{3!}=\frac{\prod _{I=2.5}^{4.5}i}{3!}=\frac{2.5*3.5*4.5}{1*2*3} \]

\[ C_{3}^{4}=\frac{\prod _{i=3-4+1}^{3}i}{4!}=\frac{\prod _{i=0}^{3}i}{4!}=\frac{0*1*2*3}{1*2*3*4}=0 \]

\[ C_{-1}^{3}=\frac{\prod _{i=-1-3+1}^{-1}i}{3!}=\frac{\prod _{i=-3}^{-1}i}{3!}=\frac{(-3)*(-2)*(-1)}{1*2*3} \]

.......

差不多了

over

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
// 斜率优化

// 对于dp[i]=max/min(f(j)+g(j)*h(i)+H(i))形式

// 为简化描述我们可以只考虑min情况
// 我们对式子中不同的j作差
// 这里姑且用j与k表示
// 不妨设k>j
// 得到差f(k)-f(j)+h(i)*(g(k)-g(j))

// 如果k优于j那么上式<=0
// f(k)-f(j)+h(i)*(g(k)-g(j))<=0
// 如果g函数满足单调,为了方便 我们假设他单调增
// 则【f(k)-f(j)】/【g(k)-g(j)】<=h(i)
// 斜率找到,就是最大且小于h(i)的一组相邻点的斜率,这时的右端点就是dp转移式所要的东西

// 总而言之,当且仅当转移方程满足dp[i]=max/min(f(j)+g(j)*h(i)+H(i))形式且g函数单调
// 我们就可以斜率优化

// 重在思维与推导,不在板子,此板子仅供参考
#include<bits/stdc++.h>

using namespace std;
#define ll long long
const int maxn = 5e4;
long long Q[maxn], dp[maxn], s[maxn];

long long f(int j) {
return dp[j] + (j + s[j]) * (j + s[j]);
}

double Slope(long long j, long long k) //求斜率
{
return double(f(k) - f(j)) / (k + s[k] - j - s[j]);
}

int main() {
ll n, L;
while (~scanf("%lld%lld", &n, &L)) {
for (int i = 1; i <= n; i++) {
int tmp;
scanf("%d", &tmp);
s[i] = s[i - 1] + tmp;
}

int Left = 1, Right = 1;
Q[1] = 0;
dp[0] = 0;
for (int i = 1; i <= n; i++) {
while (Left < Right && Slope(Q[Left], Q[Left + 1]) <= 2 * (s[i] + i - L - 1))
Left++; //维护队首(删除非最优决策)
int j = Q[Left];
dp[i] = dp[j] + (i - j - 1 + s[i] - s[j] - L) * (i - j - 1 + s[i] - s[j] - L); //计算当前f
while (Left < Right && Slope(Q[Right - 1], Q[Right]) >= Slope(Q[Right], i))
Right--; //维护队尾(维护下凸包性质)
Q[++Right] = i; //入队
}
printf("%lld\n", dp[n]);
}
return 0;
}
// solved pzoj 1010

暴力枚举因子法

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
//素数筛与合数分解
//预处理O(sqrt(n)),询问O(sqrt(n))
//调用find_ini() getfac()
const int maxn=3e6+5;
int prime[maxn],prime_,not_prime[maxn]={1,1};

void prime_ini(){// 素数不可能筛到longlong范围
for(int i=2; i<maxn; i++){
if(!not_prime[i])prime[prime_++]=i;//把质数收录
for(int j=0; 1ll*i*prime[j]<maxn; j++){
not_prime[i*prime[j]]=1;//对每一个数字枚举他的最小因子
if(i%prime[j]==0)break;//在往后的话就不是最小因子了
}
}
}

int fac[100][2],fac_;
void getfac(int x){ // assert(x>=2)
fac_=0;//清空fac
for(int i=0; prime[i]<=x/prime[i]; i++){
if(x%prime[i]==0){
fac[fac_][0]=prime[i];
fac[fac_][1]=0;
while(x%prime[i]==0){
fac[fac_][1]++;
x/=prime[i];
}
fac_++;
}
}
if(x!=1){
fac[fac_][0]=x;
fac[fac_][1]=1;
fac_++;
}
}

记录最小因子法

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

//这个板子只能处理正数
//预处理O(n)合数分解O(lgn)
//最大使用范围[1,MAXN),实际使用[1,MAXN);
//调用find_ini() getfac()
typedef long long ll;
const ll MAXN=1e6+5;
ll prime[MAXN],prime_;
ll min_fac[MAXN]={-9527,1};//0,1
bool not_prime[MAXN]={true,true};//0,1

void prime_ini(){
for(ll i=2; i<MAXN; i++){
if(!not_prime[i]){
prime[prime_++]=i;//把质数收录
min_fac[i]=i;
}

for(ll j=0; j<prime_ && i*prime[j]<MAXN; j++){
not_prime[i*prime[j]]=true;//对每一个数字枚举他的最小因子
min_fac[i*prime[j]]=prime[j];
if(i%prime[j]==0)break;//在往后的话就不是最小因子了
}
}
}

//当x=0,1会异常,无意义的东西
ll fac[100][2],fac_;
void getfac(int x){
fac_=0;
while(x!=1){
ll little=min_fac[x];
fac[fac_][0]=little;
fac[fac_][1]=0;
while(little!=1 && min_fac[x]==little){
x/=little;
fac[fac_][1]++;
}
fac_++;
}
}
//solved poj-1365

PollaraRho随机分解法

我们使用米勒罗宾素数测试多次,只要无法通过测试,则这个数必然是合数,然后使用PollaraRho随机分解法对素数进行分解。考虑gcd,如果\(gcd(a,b)\)不为1或者b,那么这个数一定是b的因子,可以用来分解b,一个数的因子很少,但是和gcd不为1或b的数有很多个(至少是\(\sqrt{b}\)个),所以我们多次随机生成,一定能够得到他的因子。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 I;
/*
* 素数
* 欧拉定理
* 费马小定理1 若a为整数,p为质数,则 pow(a,p)%p=a%p
* 费马小定理2 若a为整数,p为质数,a不是p的倍数 则 pow(a,p-1)%p=1%p=1 (0是2的0倍)
*/
namespace amazing{
inline ll gcd(ll a,ll b){
int shift=__builtin_ctzll(a|b);
b>>=__builtin_ctzll(b);
while(a){
a>>=__builtin_ctzll(a);
if(a<b) swap(a,b);
a-=b;
}return b<<shift;
}
inline ll mul(ll x,ll y,ll p){// 有误差,要当心使用,wa了可能就是因为他
ll z=(long double)x/p*y;
ll res=x*y-z*p;
return res<p?res+p:res>p?res-p:res;
}
}

ll qpow(ll a,ll b,ll c){
ll r=1;
while(b){
if(b&1) r=I(r)*a%c;
a=I(a)*a%c;
b>>=1;
}return r;
}
bool miller_rabin(ll n){// O(10*lgn)
if(n<=1) return false;
ll t=n-1,k=0;
while((t&1)==0) t>>=1,k++;
for(int i=1;i<=10;i++){// 8-10次
ll a=qpow(rand()%(n-1)+1,t,n);//全部复杂度在这
for(ll j=1;j<=k;j++){
ll nex=I(a)*a%n;
if(nex==1&&a!=1&&a!=n-1) return false;//通不过测试,是合数
a=nex;
}
if(a!=1)return false;//通不过测试,是合数
}
return true;// 通过测试可能是伪素数
}
ll pollard_rho(ll n){ // assert(n>1)
while(true){
ll c=rand()%(n-1)+1;
ll x=0,y=0,val=1;
for(ll i=0;;i++){
x=amazing::mul(x,x,n)+c;
if(x>n)x-=n;
// x=(I(x)*x+c)%n;
if(x==y) break;
val=amazing::mul(val,abs(x-y),n);
// val=I(val)*abs(x-y)%n;// 乘起来是根据 gcd(a,n)|gcd(ab,n)恒成立 且gcd(ab,n)=gcd(ab%n,n)
if((i&-i)==i||i%127==0){// 太多必然导致val趋于n,太少导致gcd拖慢速度
ll d=__gcd(val,n);// 乘起来一起算
if(d==n) break;
if(d>1) return d;
}
if((i&-i)==i) y=x;
}
}
}

vector<ll> findfac(ll n){
vector<ll>res,stk(1,n);
if(stk.back()==1) return res;
while(!stk.empty()){
ll top=stk.back();stk.pop_back();
if(miller_rabin(top)) res.push_back(top);
else{// 通不过测试是合数
ll fac=pollard_rho(top);
stk.push_back(fac);
stk.push_back(top/fac);
}
}
return res;
}

ll read(){ll x;scanf("%lld",&x);return x;}

int main(){
srand(time(NULL));
for(int T=read();T>=1;T--){
vector<ll>v=findfac(read());
sort(v.begin(),v.end());
if(v.size()==1) printf("Prime\n");
else printf("%lld\n",v.back());
}
}

给个n,让你构造一个\(n\times n\)的矩阵满足每一行每一列都是1-n的排列且对于所有的i!=j都有A[i,j]!=A[j,i]

​ 奇数很好处理,但是偶数不好搞,

​ 对于一个偶数2k

​ 我们假设构造出了k*k的矩阵B是成立的了

​ 看这个矩阵C[i,j]=B[i,j]+k

​ C B1

​ B2 C

​ 我们把B1沿着自己的主对角线翻转

​ 那么现在B2与B1关于2k*2k主对角线对称

​ 我们让B2中的1变成2,2变成3,3变成4

​ 构造完成

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
99
100
101
102
103
104
105
106
107
108
// 最低位的1 ->                  x&-x
// 去掉最低位的1 -> x&(x-1)
// 有效数字全是1 -> (x&(x+1))==0
//把最低位的0 变成1-> x|(x+1)
//取出最低位的0并变成1 (~x)&(x+1)
//取出第k位(约定最低位为第0位) x&(1<<k)


/* all

bit cnt one -> cnt_one(x) -> int __builtin_popcount (unsigned int x);
bit rev -> rev_dig(x) ->
high bit -> high_one(x)
count leading zero -> cnt_leading_zero(x) -> int __builtin_clz (unsigned int x);
count trailing zero -> cnt_trailing_zero(x) -> int __builtin_ctz (unsigned int x);
get trailing one -> get_trailing_one(x) -> x&(x^(x+1))

*/
typedef unsigned int u32;
namespace bit{

//count the digits of one in binary number
u32 co[65536u];//bit cnt one
void cnt_one_ini() {
for (u32 i = 1; i < 65536u; i++)
co[i] = co[i >> 1] + (1 & i);
}
u32 cnt_one(u32 x) {
return co[x & 0xffffu] + co[x >> 16];
}


//reverse the digits in binary number
u32 rd[65536u];//bit rev data
void rev_digit_ini() {
for (u32 i = 1; i < 65536u; i++)
rd[i] = (rd[i >> 1] >> 1) | ((i & 1) << 15);
}
u32 rev_dig(u32 x) {
return rd[x >> 16] | (rd[x & 0xffffu] << 16);
}


//get the highest digit one in binary number
u32 ho[65536u];//high bit data
void high_one_ini(){
ho[1]=1;
for(u32 i=2;i<65536u;i++){
ho[i]=ho[i>>1]<<1;// only the one have the highest digit one 1;
}
}
u32 high_one(u32 x){
return x<65536u ? ho[x]:(ho[x>>16]<<16);
}


//count leading zero
u32 clz[65536u];//leading zero count
void cnt_leading_zero_int(){
clz[0]=16;
for(u32 i=1;i<65536u;i++){
clz[i]=clz[i>>1]-1;
}
}
u32 cnt_leading_zero(u32 x){
if(x<65536u){
return clz[x]+16;
}
else {
return clz[x>>16];
}
}

//count trailing zero
u32 ctz[65536u];//trailing zero count
void cnt_trailing_zero_int(){
ctz[0]=16;
for(u32 i=1;i<65526u;i++){
ctz[i]=i&1 ? 0: ctz[i>>1]+1;
}
}
u32 cnt_trailing_zero(u32 x){
if(x<65536u){
return ctz[x];
}
else {
return ctz[x&65535u];
}
}

//count leading one is more diffcult using count leading zero


//提取第k个1
int kthbit(u32 x, int k) {
int s[5], ans = 0, t;
s[0] = x;
s[1] = x - ((x & 0xAAAAAAAAu) >> 1);
s[2] = ((s[1] & 0xCCCCCCCCu) >> 2) + (s[1] & 0x33333333u); s[3] = ((s[2] >> 4) + s[2]) & 0x0F0F0F0Fu;
s[4] = ((s[3] >> 8) + s[3]) & 0x00FF00FFu; t = s[4] & 65535u;
if (t < k) k -= t, ans |=16, x >>=16;
t = (s[3] >> ans) & 255u;
if (t < k) k -= t, ans |= 8, x >>= 8; t = (s[2] >> ans) & 15u;
if (t < k) k -= t, ans |= 4, x >>= 4; t = (s[1] >> ans) & 3u;
if (t < k) k -= t, ans |= 2, x >>= 2; t = (s[0] >> ans) & 1u;
if (t < k) k -= t, ans |= 1, x >>= 1; return ans;
}
};

博弈常常是acm中的签到题,能不能快速拿下,这得看本事。

局面决定一切

首先有以下的结论:

  • 胜负取决于局面
  • 如果当前局面能转移给对手的一个输的局面,那么对手就输
  • 如果当前局面转转移给对手的全是赢的局面,那么对手就赢

依据上诉三条规则,博弈题目也可以通过模拟来实现找规律

例题1

有a,b两个数字,两人轮流操作,每次可以选择两个之中较小的数字,然后另一个数字减去选择数字的任意倍数(不能减到负数),直到其中一个为0,不能操作为败。比如2,8可以转移为(2,6)(2,4)(2,2)(2,0)

题解

不妨设\(a\ge 2b\)

  • 如果局面(a%b+b,b)先手赢,则局面(a,b)先手就赢

  • 如果局面(a%b+b,b)先手输,则a,b先手可以花样拿使得后手得到(a%b+b,b), 最后先手还是赢

对于其他a,b其实只有一种拿法,简单处理一下,细心就行了

例题2

有一个从1到n的连续自然数序列,两人轮流操作,可以选取一个数字,拿走它的所有因子(如果序列中存在),直到一方无法拿,该方输。

题解

我们先考虑一个这个序列2,3,4,5,6......n,

  • 如果先手输,题目的序列中我们就拿1,题目中先手赢

  • 如果先手赢,先手总得拿一个吧,假设他拿的x,题目中我们也拿x,题目中先手赢

例题3

鲍勃和爱丽丝正在玩一款新游戏。 有n个盒子从1到n编号。 每个盒子都是空的或包含几张卡片。 鲍勃和爱丽丝依次移动卡片。 在每个回合中,相应的玩家应该选择非空框A,然后选择另一个框B,其中B <A &&(A + B)%2 = 1 &&(A + B)%3 = 0。 然后,从方框A取任意数量(但不是零)的牌到方框B。最后一个可以进行合法移动的人获胜。 爱丽丝是第一个玩家。 请预测谁将赢得比赛。

题解

我们发现1,3,4是无法操作的盒子

有且仅有这三个盒子,

我们按照n%6=1,3,4和n%6=0,2,5把所有的盒子分为两类

考虑二分图模型,这就是一个二分图模型

除了1 3 4以外,所有其他点都存在出度,我们可以想象,比赛结束时所有卡片都在1 3 4 中

那么第一类盒子,不影响比赛结果,

因为每当对手操作了第一类盒子,我们可以操作第二类盒子让这些卡转移到1 3 4 中并恢复到对手上一次操作前到第二类盒子状态,

那么右边的盒子问题就是一个NIM问题

例题4

有一个\(n\times n\)的网格,左下角有一个东西可以在格子里面走,可以往相邻的格子走,已经走过的格子不能再走,两人轮流走,谁不能走谁输

题解

只要当前可以走的区域数目为奇数那么就可以赢,除非对手想打破这个僵局,也就是说,对手走了一步之后,把可以走的区域分成了两部分,只能选择其一,那么我们肯定选取走完之后剩余可以走的格子数为奇数部分那边走啊,也就是说\(n*n-1\)为奇数先手就赢了,也就是n为偶数先手就赢了。

例题5

有n张牌,两个人轮流抓牌,只能抓二的某个幂次方张牌,谁拿最后一张牌谁赢

题解

n%3==0,先手一定输,因为先手拿了以后一定会变成非三的倍数,后手可以拿1张或两张使得n回到三的倍数,局面还原,直到n=3,先手就输了。

至于其他的博弈题目,一般不是那么容易找到规律的,所以产生了新的算法来模拟博弈进行

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
//sgf是转移方法
//sgs是前一个状态的集合
int sgf[N],sg[N];
bool sgs[N];
void sgf_ini(){
sgf[0]=1;
sgf[1]=1;
sgf[2]=2;
for(int i=3;i<20;i++){
sgf[i]=sgf[i-1]+sgf[i-2];
//cout<<sgf[i]<<endl;
}
}
void sg_ini(int n){
sgf_ini();
//sg[0]=0;
for(int i=1;i<=n;i++){
memset(sgs,0,sizeof(sgs));
for(int j=1;/**/i-sgf[j]>=0;j++)sgs[sg[i-sgf[j]]]=true;
for(int j=0;;j++)if(!sgs[j]){
sg[i]=j;
break;
}
}
//for(int i=0;i<=n;i++){
// printf("%4d %2d",i,sg[i]);
// if(i%10==9)cout<<endl;
//}
}

博弈并不是公平的,博弈的胜负取决于博弈当前的局面。

必胜态的后继中一定有一个必败态

必败态的后继中一定全是必胜态

这其实可以对应到一个运算法则mex集合运算

mex运算:集合中不存在的最小的非负整数

我们定义0为失败,其他数字为胜利,(这里我并不理解为什么要用其他数字而不是1,肯能是还有其他用途)

对于sg[i],我们参考dp算法

假设nex是i的后继,那么sg[i]=mex{sg[nex1],sg[nex2],sg[nex3]。。。