Jμdge

编辑于 2020-10-17 12:09

+ 关注

【题解】牛客挑战赛44 精

比赛中途因为一些问题更正了题面，再次为带来的麻烦道歉【抱拳

另外由于出题人是新手出题人，没有出过几次题，题目中的小漏洞有些多，敬请谅解

Std 代码：

A 孪生的孪生素数对
 B 无限电阻
 C 有用的 LCM
D 数列的和
 E 巨阵
 F 斐波那契？数列！

T1

第一题，只要对输入进行判断，n 是否大于等于 7 即可，小于 7 则输出 0 ，否则输出 1 3 5 7 ，因为孪生的孪生素数对只有这么一个，知道（猜到）这个结论就可以轻松通过本题

下面考虑证明，根据题意可得，我们需要求的实际上是满足 x ， x+2 和 x+4 均为质数的三元组 (x,x+2,x+4) 的数量，我们首先对其进行膜三处理，可得： $x≡ k （MOD\ 3）\\ x+2≡ k+2 (MOD\ 3)\\ x+4 ≡ k+1 (MOD\ 3)$
∵ k,k+1,k+2 三个数在膜 3 意义下取遍 0,1,2

∴三个数中必然有一个 3 的倍数

又 ∵ 三个数均为质数

∴ 三个数中为三的倍数的那个数为 3

由于 3 是最小的奇质数，所以 x 只能取 3 ，于是 x+2 = 5, x+4 = 7 ，发现三个数均为质数，满足条件

所以孪生的孪生素数对所对应三元组仅有 (3,5,7) 这一个（据 HgS 聚聚所说这题是假题，自然是放在第一题的）

T2

根据简单的电压计算方法可得，两点之间的电压为两点间某一条路线上每一段导线上的电压之和，那么我们只需要搜一下得到两点间的路径长，然后根据 $I * R$ 可以算出每段导线两端的电压，进行累加最后除去 $I$ 就好了（据 Venus 聚聚说这是初中题，口头讲了讲做法发现是随便切的于是就叫咱滚蛋了）

列下几个坑点（No Answer 的情况）：

1~n 不连通
某一段导线上的电流大小比 I 大
某一个节点出发绕一圈回来发现电位改变了（即有环上的边权总和不为 0 ）
某一个节点的电位比 1 号点的电位大或者比 0 小

详情当然是康代码

另外之前有同学验题的时候质疑电流守恒定律好像没有用到
然后发现确实没有考虑这个东西（于是出题人验题人们纷纷背锅），后来讨论之后决定不考虑这些定理

T3

欧拉筛变形与 min_25 筛结合，难度适中，可能会比较卡常，min25 筛是板子

欧拉筛直接 $O(\sqrt n ·log~ log~ n)$ （或者是 O (能过) 的复杂度）筛出质数个数就好了

详情见代码即可

然后发现数据很水直接 min_25 就 ac 了，貌似用其他算法 ac 的人也说（无*** 说，思考人生中...

不过我在众巨佬的代码中也发现了更好的做法（我就不来翻译人家的代码的思路了

具体代码提交记录中搜索 [Heltion] 即可

T4

简单的 FFT 多项式快速幂后累加即可得到答案，然后发现 T 了

于是考虑推式子用 O(n) 做法

$\text{令}F(x)=\sum_{i=1}((i+k)^2-k^2)x^i\text{，则有:}\\ \begin{aligned} F(x)&=\sum_{i=1} i^2x^i +2k\sum_{i=1}ix^i\\ &=\frac{x(1+x)}{(1-x)^3}+\frac{2k·x}{(1-x)^2}\\ &=\frac{x\big((1+2k)+(1-2k)x\big)}{(1-x)^3}\\ \end{aligned} \\ \begin{aligned} Ans&= \sum_{i=n}^m (m-i)· [x^i]F^n(x) \end{aligned} \\ \text{令}G(x)=\sum_{i=0} i·x^i \text{则有：}\\ \begin{aligned} Ans&=[x^m]G(x)*F^n(x)\\ &=[x^m]\frac x{(1-x)^2}·\frac{x^n\big( (1+2k)+(1-2k)x\big)^n}{(1-x)^{3n}}\\ &=[x^{m-n-1}]\frac{\big( (1+2k)+(1-2k)x\big)^n}{(1-x)^{3n+2}}\\ &=[x^{m-n-1}]\Big(\sum_{i=0}C_{3n+i+1}^ix^i\Big)\Big(\sum_{i=0}^nC_n^i (1+2k)^{n-i}(1-2k)^i·x^i\Big) \end{aligned}\\$

于是就可以 O(n) 预处理然后 O(n) 求解了

详情见代码

T5

答案：对于大小为 n*n 的方阵，方阵的最大价值为 $\lfloor \frac{n^2}{2} \rfloor -1$

Proof：

将两个相邻格子作为一个二元格，将四个相邻格子（左上左下右上右下四个格子）作为一个四元格。则易知四元格是有贡献的格子当且仅当其内部恰有三个二元格在四元格范围内顺时针递增，且可以证明顺时针递增二元格的个数小于四（否则顺时针方向上恒增，与常理违背），且大于零（否则顺时针方向上恒减，与常理违背）

并且我们可以发现每个二元格，除了最外围的那些两个格子都与边界线相贴的二元格外，每个二元格都能产生一点贡献，而所有外围边线二元格产生的最多总贡献为 $4(n-1)-1$ ，最后面减去 1 是因为最外围的所有数形成的环不可能顺时针恒增，必然有一个二元格顺时针降序，否则与常理违背

然后我们设所有二元格总贡献为 K ，有贡献的四元格个数位 k ，那么有：
$ $\begin{cases} K\le 4(n-1)-1+2(n-2)(n-1) =2n(n-1)-1 ……① \\ K\ge 3k+(n-1)^2-k=2k+(n+1)^2……② \end{cases}$ $联立 ① ② 两式，得：$ 2k\le n^2-1$

又因为 $k ∈ Z^*$ ，所以 $k\le \lfloor\frac {n^2} 2 \rfloor -1$

综上，我们证明了有贡献的四元格的上限值，并且可以根据取等条件得到取到上界的条件：

最外围的二元格贡献最大化
除了有贡献的四元格外，无用四元格内部的二元格贡献值尽量为 1

于是我们尝试先构造 n 为偶数的情况：

螺旋排布，不满足条件（2）
树枝排布，不满足条件（2）
蛇形排布，左侧一列不满足条件（1）
改造后的蛇形排布，满足两个条件，且取到上限值

（图先欠着）

考虑 n 为奇数的情况，首先发现如果要取到上限值，那么有一个四元格内会包含两个有贡献的二元格。粗略估计这个格子的位置肯定比较特殊，大概就是四个角落与起点终点，并且四个角落贡献基本最大，难以修改，于是考虑起点终点，其中起点也难以修改，于是考虑终点那一个部分，发现只要把最后两行单独尽心蛇形排布即可满足上限值

这道题被 spj 编译错误卡的同学不用担心罚时影响，那几次是系统技术错误，提交不计入罚时

原因貌似是加了 spj 之后 register 出现了定义问题，和题目本身无关

另外本题其实是一道数竞题（刷题多的数信双修巨佬可能秒切？据验题人说是没事，于是放上来了

代码本身难度并不大 ~~也就是高中信息模拟题~~

T6

第一个小部分属于套路提：直接考虑拆分表达式转矩阵加速递推，以 $a_i , a_i^2$ 等的元素数值为矩阵中的项然后找找递推关系就可以做出来了

第二个小部分属于思维题：

直接颓式子： $\begin{aligned} ANS&= \frac 1 5 \sum_n f_i^2 \\ &= \frac 1 5 \sum_n \Big((\frac{1+\sqrt5} 2)^i - (\frac{1-\sqrt5} 2)^i\Big)^2 \\ &= \frac 1 5 \sum_n \Big((\frac{3+\sqrt5} 2)^i + (\frac{3-\sqrt5} 2)^i -2*(-1)^i\Big) \\ &= \frac 1 5 \Big( \frac{3+\sqrt5} 2*{ \frac{ (\frac{3+\sqrt5} 2)^n-1}{\frac{3+\sqrt5} 2-1} } +\frac{3-\sqrt5} 2*{ \frac{ (\frac{3-\sqrt5} 2)^n-1}{\frac{3-\sqrt5} 2-1} } + 1-(-1)^n \Big) \\ &= \frac 1 5 \Big( \frac{(1+\sqrt5)}2*\big({ (\frac{3+\sqrt5} 2)^n-1}\big) +\frac{(1-\sqrt5)}2*\big({ (\frac{3-\sqrt5} 2)^n-1}\big) + 1-(-1)^n \Big) \\ &= \frac 1 5 \Big( \frac{(1+\sqrt5)}2* (\frac{3+\sqrt5} 2)^n +\frac{(1-\sqrt5)}2*(\frac{3-\sqrt5} 2)^n-(-1)^n \Big) \end{aligned}$
然后我们可以定义一些常量：

令 $f1 =\frac{3+\sqrt5}2 ,f2=\frac{3+\sqrt5}2, A1=\frac{1+\sqrt5}2 , A2=\frac{1-\sqrt5}2$

那么答案就可以简化为：

$ANS=5'*(A1*f1^n+A2*f2^n -(-1)^n)$

然后接下来考虑如何把 根号五 在模 998244353 下表示出来

首先想到的肯定是二次剩余，但打开板子输进去 5 998244353 后发现这个模数下不存在二次剩余，于是我们只能考虑别的方法

（二次剩余与此题解法无关，没学过的同学可以自己百度，下面附一下二次剩余的代码 ~~不过这玩意儿拿去用就行了，别想着先弄明白了，毕竟咱都忘了自己以前写的啥来着了，只记得要随机个啥子~~）

//by Judge
#include<bits/stdc++.h>
#define CCF Coin_Collecting_Foundation
#define Rg register
#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){ int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} char sr[1<<21],z[20];int CCF=-1,Z;
inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;}
inline void Out(){sr[++CCF]='E',sr[++CCF]='R',sr[++CCF]='R',sr[++CCF]='O',sr[++CCF]='R',sr[++CCF]='\n';}
inline void print(int x,char chr='\n'){
    if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10); while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr;
} int n,mod,a,v,p;
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int inc(int x,int y){return (x+=y)>=mod?x-mod:x;}
inline int qpow(int x,int p=mod-2){ int s=1; for(;p;p>>=1,x=mul(x,x)) if(p&1) s=mul(s,x); return s; }
struct cp{ int x,y,c; cp(){} inline cp(int _x,int _y,int _c){ x=_x,y=_y,c=_c; }
    cp operator *(const cp& b){ return cp(inc(mul(x,b.x),mul(mul(y,b.y),c)),inc(mul(x,b.y),mul(y,b.x)),c); }
    cp operator ^(int p){ cp x=*this,s=cp(1,0,c); for(;p;p>>=1,x=x*x) if(p&1) s=s*x; return s; }
}x;
inline void Calc(){ n=read(),mod=read(),n%=mod,a=0,v=mod-n;
    if(!n) return print(0),void(); if(qpow(n,(mod-1)>>1)!=1) return Out(),void();
    while(qpow(v,(mod-1)>>1)==1) a=rand()%mod,v=inc(mul(a,a),mod-n);
    p=(mod+1)>>1,x=cp(a,1,v)^p,(x.x*2>mod)&&(x.x=mod-x.x),print(x.x,' '),print(mod-x.x);
}
int main(){
    srand(time(NULL)),Calc(); return Ot(),0;
}

（输入 5 998244353 发现输出是 ERROR 怎么样我没骗你吧）

不过 5 在模 1e9+9 下倒是有二次剩余的，只不过这个出题人比较坏（指了指自己）就没有用这个模数

那另一个办法就是转类复数域了（这名称就是我在胡扯，老年人记性不好不记得这玩意儿叫啥了）

首先我们考虑让复数域的第一维表示 1 的倍数，然后让第二维表示 $\sqrt5$ 的倍数，接着定义这个域下的乘法：

$(x_1,y_1)*(x_2,y_2)=(x_1·x_2+5·y_1·y_2,x_1·y_2+x_2·y_1)$

加法的话就是对应位上的数相加，这样我们写个结构体就可以轻松通过本题了

实际比赛中发现其实有巨佬在第二问直接带矩阵的系数 AC 的情况，只能说常数小就是 6 吧

我貌似是第一问卡住了时间上限然后第二问数据就没有开太大，也没有刻意去卡第二问的矩阵做法，总之就是把这种做法放过了，问题不大把（就是题目变水了区分度小了

总的来说，这次比赛就是用心出题目，用脚造数据，用想象验题吧 /kk

题目都能做，也都有人 ac ，算是没有出完全的废题吧

2025最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(6) 回帖

加载中...

话题同步到我的动态回帖

【题解】牛客挑战赛44 精

Std 代码：

T1

T2

T3

T4

T5

T6

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐