NOIP信心增加赛 赛后题解
陈曦
2018-11-07 10:11:46
真的很抱歉
恭喜@陈曦ioa rank1 255
放一下题号，大家还可以继续交：U50509 U50451 U50450 U50486
# T1 White Album Gcd
~~真白学~~，还有雪菜好可爱
没想到t1锅了，真的很抱歉，出题人取模后忘了去负了，真的抱歉
## 20pts
我们发现在取gcd之前不能取模，直接算即可。
## 30-40pts
用__int128或高精。
其实我对这题有一个神奇的想法，用long double，手写取模即可，兴许能拿很多分，不过我太蒟蒻了（~~不想写~~），就算了。
## 50pts
很多人应该看出来了
$gcd(a^{n}-1,a^{m}-1)=a^{gcd(m,n)}-1$
为什么呢？下面进行证明：
前置知识：
1.如果 $a|b$ 且 $b|a$ ，那么 $a=b$。
2.分解公式：$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+...+xy^{n-2}+y^{n-1})$
3.若 $m|a,m|b$，则 $m|gcd(a,b)$ ，即 $a,b$ 的任何一个公约数都是它们最大公约数的约数。
4.若 $m>0$,则 $gcd(ma,mb)=m\times gcd(a,b)$
------------
我们设 $gcd(a^{n}-1,a^{m}-1)=D$
首先 $gcd(m,n)|n\ ,gcd(m,n)|m$ 。
由分解公式得 $(a^{gcd(m,n)}-1)|(a^n-1)$ 且 $(a^{gcd(m,n)}-1)|(a^m-1)$
由性质3可知 $(a^{gcd(m,n)}-1)|D$
我们设 $gcd(m,n)=d$ 。
列出一个扩欧公式，我们设 $mu-nv=d$。
因为 $D|(a^m-1)$，则 $D|(a^{mu}-1)$，故同样的 $D|(a^{nv}-1)$
推得 $D|(a^{mu}-a^{nv})$ 。
由公式得式① $D|a^{nv}(a^d-1)$ 。
因为 $a>1$ 且 $D|(a^m-1)$，则 $gcd(a,D)=1$ 。
进而 $gcd(a^{nv},D)=1$ 。
由性质4与式①得 $D|(a^d)-1$ 。
所以 $gcd(a^{n}-1,a^{m}-1)=a^{gcd(m,n)}-1$ 。
虽然证明繁杂，但代码还是很好打的，快速幂即可：
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
ll m,n,p;
ll gcd(ll a,ll b)
{return (b==0)?a:gcd(b,a%b);}
ll ksm(ll x,ll y)
{
ll ans=1;
while(y>0)
{
if(y&1)ans=(ans*x)%p;
x=(x*x)%p;y>>=1;
}
return ans%p;
}
int main()
{
ll x,y;
scanf("%lld%lld%lld%lld%lld",&x,&y,&n,&m,&p);
long long k=gcd(m,n);
printf("%lld",(ksm(x,k)-ksm(y,k))%p);
}
```
## 100pts
对第三个结论进行推导即可，易推出
当$gcd(x,y)=1$ 时 ，$gcd(x^a-y^a,x^b-y^b)=x^{gcd(a,b)}-y^{gcd(a,b)}$
其实网上也有相关推导，请大家自行证明。
代码与上面差不多。
其实我本来想让大家求 $\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}gcd(x^i-y^i,x^j-y^j)$
这要就要用莫比乌斯反演了，既然是noip模拟赛，就不毒瘤了
------------
# T2 珂朵莉的数列
珂朵莉赛高～～
## 0-？pts
各种骗分，话说有巨佬拿了50pts
## 100pts
有趣的题目。
许多人应该想的是二分吧，因为做过类似的，但这题并不单调，而且其实这题二分因为精度会挂。
我们来看一下式子：
$a_i=\frac{a_{i-1}+a_{i+1}}{m}+d\ (2\leqslant i\leqslant n-1)$
转化一下：
$a_{i+1}=ma_i-a_{i-1}-md\ (2\leqslant i\leqslant n-1)$
这样就可以进行递推了：
$a_3=ma_2-a_1-md$
$a_4=ma_3-a_2-md=m(ma_2-a_1-md)-a_2-md$
...
如此递推下去
$a_n=xa_1+ya_2+zd$
由于其他值已知，我们就可以得出 $a_2$，再推一次，不就得出整个序列了吗？
所以我们就将系数递推就好了，复杂度 $O(n)$
代码很短：
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
long double a[1000005];
long double f[1000005][3];
int main()
{
int n;
long double d,m;
scanf("%d",&n);
scanf("%Lf%Lf%Lf%Lf",&m,&d,&a[1],&a[n]);
if(n==2)
{printf("%.0Lf %.0Lf",a[1],a[n]);return 0;}
f[3][0]=-1,f[3][1]=m,f[3][2]=-m;
f[4][0]=-m,f[4][1]=m*m-1,f[4][2]=m*m+m;
for(register int i=5;i<=n;i++)
{
f[i][0]=m*f[i-1][0]-f[i-2][0];
f[i][1]=m*f[i-1][1]-f[i-2][1];
f[i][2]=m*f[i-1][2]-f[i-2][2];
f[i][2]-=m;
}
a[2]=(a[n]-f[n][0]*a[1]-f[n][2]*d)/f[n][1];
for(register int i=3;i<=n-1;i++)
a[i]=m*a[i-1]-a[i-2]-m*d;
for(register int i=1;i<=n;i++)
printf("%.0Lf ",a[i]);
}
```
其实 $f,a$ 数组的内存还可以滚掉，我就不毒瘤卡空间了。
------------
# T3 没有你的世界，毁了也无所谓
~~由乃酱好可爱~~
## 注意：T3 l不一定小于r，请自行判断
我真的不是故意毒瘤大家的，只是想提醒大家，真的抱歉
这是道水题？
区间修改加区间求和？
前面十分友好，突然看到了取模。
于是 $[l,r]$ 的平均数为 $(\sum\limits_{i=l}^{r}a_i)/(r-l+1) \mod 11111597780929$
## 30pts
暴力加逆元即可。
## 100pts
逆元搞上来啊！！！
费马小，扩欧，欧拉。
等等，我们把 $11111597780929$ 丢到计算器里分解一波质因数。
$11111597780929=1111151\times 10000079$
完了，不是质数，逆元完蛋。
等等，序列长度不大于 $10^6$ ，比分解的两个质数都要小，那么肯定 $gcd(r-l+1,11111597780929)=1$
许多人好奇是不是样例错了，其实是费马小用错了，这里不能用
扩欧，欧拉都可以。
还有一个小问题：$11111597780929>\sqrt{2^{64}-1}$
会爆 $long\ long$ ，高精岂不是太麻烦（~~毒瘤~~）？
我们有快速乘
```cpp
LL mul(LL a, LL b, LL P)
{
LL ans = 0;
for(; b; b >>= 1, (a <<= 1) %= P)
if(b & 1) (ans += a) %= P;
return ans;
}
```
复杂度$O(m\ log\ n)$吧。
所以完整代码如下（分块（PS.~~分块可以过~~））
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const ll mod=11111597780929;
ll a[2000010],sum[2000010],tag[2000010];
int block[2000010];
int n,m,sqr;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void write(ll x)
{
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline ll mul(ll a,ll b)
{
ll ans = 0;
for(;b;b>>=1,(a<<=1)%=mod)
if(b&1)(ans+=a)%=mod;
return ans;
}
ll x,y,k;
void exgcd(ll a1,ll b1)
{
if(!b1)
{x=1;y=0;return;}
exgcd(b1,a1%b1);
k=x;x=y;
y=k-a1/b1*y;
return;
}
inline void add(int l,int r,ll c)
{
for(register int i=l;i<=min(block[l]*sqr,r);++i)
{
a[i]+=c,a[i]%=mod;
sum[block[l]]+=c;
sum[block[l]]%=mod;
}
if(block[l]!=block[r])
for(register int i=(block[r]-1)*sqr+1;i<=r;++i)
{
a[i]+=c,a[i]%=mod;
sum[block[r]]+=c;
sum[block[r]]%=mod;
}
for(register int i=block[l]+1;i<=block[r]-1;++i)
tag[i]+=c,tag[i]%=mod;
}
inline ll query(int l,int r)
{
ll ans=0;
for(register int i=l;i<=min(block[l]*sqr,r);++i)
{
ans+=a[i]+tag[block[l]];
ans%=mod;
}
if(block[l]!=block[r])
for(register int i=(block[r]-1)*sqr+1;i<=r;++i)
{
ans+=a[i]+tag[block[r]];
ans%=mod;
}
for(register int i=block[l]+1;i<=block[r]-1;++i)
{
ans+=sum[i]+sqr*tag[i];
ans%=mod;
}
return ans;
}
int main()
{
memset(tag,0,sizeof(tag));
n=read(),m=read();
sqr=sqrt(n);
for(register int i=1;i<=n;++i)
a[i]=read();
for(register int i=1;i<=n;++i)
{
block[i]=(i-1)/sqr+1;
sum[block[i]]+=a[i];
}
for(register int i=1;i<=m;i++)
{
int opt=read(),l=read(),r=read();
if(l>r)swap(l,r);
if(opt==1)
{
ll k=read();
add(l,r,k);
}
else
{
exgcd(r-l+1,mod);
ll ans=mul(x,query(l,r))+mod;
printf("%lld\n",ans%mod);
}
}
return 0;
}
```
以下是线段树代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 4000010
using namespace std;
typedef long long ll;
ll n,m,l,r,z;
struct node
{ll data,tag;}
tree[maxn];
ll a[maxn],k;
const ll mod=11111597780929;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
template <typename _TpInt>
inline void write(_TpInt x)
{
if(x<0){putchar('-');write<_TpInt>(~x+1);}
else{if(x>9)write<_TpInt>(x/10);putchar(x%10+'0');}
}
void build(ll x,ll l,ll r)
{
if(l==r)
{tree[x].tag=0;tree[x].data=a[l];return;}
ll mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
tree[x].data=tree[x<<1].data+tree[x<<1|1].data;
tree[x].tag=0;
}
void down(ll x,ll l,ll r)
{
ll mid=(l+r)>>1;
tree[x<<1].data+=tree[x].tag*(mid-l+1);
tree[x<<1].tag+=tree[x].tag;
tree[x<<1|1].data+=tree[x].tag*(r-mid);
tree[x<<1|1].tag+=tree[x].tag;
tree[x].tag=0;
}
void add(ll x,ll l,ll r,ll maxl,ll maxr,ll k)
{
if(l==maxl&&r==maxr)
{
tree[x].data+=k*(r-l+1);
tree[x].tag+=k;
tree[x].data%=mod;
tree[x].tag%=mod;
return;
}
ll mid=(l+r)>>1;
down(x,l,r);
if(maxr<=mid)
add(x<<1,l,mid,maxl,maxr,k);
else if(maxl>mid)
add(x<<1|1,mid+1,r,maxl,maxr,k);
else
{
add(x<<1,l,mid,maxl,mid,k);
add(x<<1|1,mid+1,r,mid+1,maxr,k);
}
tree[x].data=tree[x<<1].data+tree[x<<1|1].data;
tree[x].data%=mod;
}
ll getsum(ll x,ll l,ll r,ll maxl,ll maxr)
{
if(l==maxl&&r==maxr)
return tree[x].data%mod;
ll mid=(l+r)>>1;
down(x,l,r);
if(maxr<=mid)
return getsum(x<<1,l,mid,maxl,maxr)%mod;
else if(maxl>mid)
return getsum(x<<1|1,mid+1,r,maxl,maxr)%mod;
return (getsum(x<<1,l,mid,maxl,mid)%mod+getsum(x<<1|1,mid+1,r,mid+1,maxr)%mod)%mod;
}
inline ll mul(ll a,ll b)
{
ll ans = 0;
for(;b;b>>=1,(a<<=1)%=mod)
if(b&1)(ans+=a)%=mod;
return ans;
}
ll x,y,t;
void exgcd(ll a1,ll b1)
{
if(!b1)
{x=1;y=0;return;}
exgcd(b1,a1%b1);
t=x;x=y;
y=t-a1/b1*y;
return;
}
int main()
{
n=read(),m=read();
for(register ll i=1;i<=n;++i)
a[i]=read(),a[i]%=mod;
build(1,1,n);
for(register ll i=1;i<=m;++i)
{
z=read(),l=read(),r=read();
if(r<l)swap(l,r);
if(z==1)
{k=read(),add(1,1,n,l,r,k);}
else
{
exgcd(r-l+1,mod);
ll ans=mul(x,getsum(1,1,n,l,r))+mod;
printf("%lld\n",ans%mod);
}
}
}
```
------------
# T4 最佳狙击点
亚里亚也好可爱
## 15pts
暴力枚举。
## 25pts
暴力枚举+求中位数（对于特殊数据）
## 75-100pts
明眼人一下就可以看出来，这是（~~计算几何~~）模拟退火。
你们可能会说我毒瘤，退火题还oi赛制。
但我就是想告诉大家，在 noip 这种 oi 赛制的比赛中，退火等随机算法要慎用。
这题算法简单，就是随机一个坐标，更新一下最大值。
但怎么会这么简单？
我们首先来看一下复杂度：
我们先做一个试验：
```cpp
double delta=0.995;
double t=2000,tmin=1e-8;
int main()
{
long long pos=0;
while(t>tmin)
pos++,t*=delta;
printf("%lld",pos);
}
```
当参数为以上时，迭代了5192次。
复杂度就是$O(5192\times n)$，勉强可以跑一次。
而许多人一上手就不管，直接弄个两三次，不t才怪。
我又试了试迭代系数为0.95，发现又wa了一个点。
所以我希望大家认识到，退火算法虽好，但也需要优秀的调参，也要分析一下复杂度。
代码如下：
```cpp
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cmath>
using namespace std;
struct node{long double x,y,z,w;}a[5010];
int n,totx,toty,totz;
long double ansx,ansy,ansz;
long double ans=1e40,t,tmin=1e-14;
const long double delta=0.995;
long double energy(long double x,long double y,long double z)
{
long double pos=0;
for(register int i=1;i<=n;i++)
{
long double deltax=x-a[i].x,deltay=y-a[i].y,deltaz=z-a[i].z;
pos+=sqrt(deltax*deltax+deltay*deltay+deltaz*deltaz)*a[i].w;
}return pos;
}
void SA()
{
long double x=ansx,y=ansy,z=ansz;
t=2000;
while(t>tmin)
{
long double posx=x+((rand()<<1)-RAND_MAX)*t;
long double posy=y+((rand()<<1)-RAND_MAX)*t;
long double posz=z+((rand()<<1)-RAND_MAX)*t;
long double now=energy(posx,posy,posz);
long double delta2=now-ans;
if(delta2<0)
{
x=posx;y=posy;z=posz;
ansx=x;ansy=y;ansz=z;ans=now;
}
else if(exp(-delta2/t)*RAND_MAX>rand()) x=posx,y=posy,z=posz;
t*=delta;
}
}
int main()
{
srand(19260817); srand(rand()); srand(rand());
scanf("%d",&n);
for(register int i=1;i<=n;i++)
{
scanf("%Lf%Lf%Lf%Lf",&a[i].x,&a[i].y,&a[i].z,&a[i].w);
totx+=a[i].x;toty+=a[i].y;totz+=a[i].z;
}
ansx=(long double)totx/n,ansy=(long double)toty/n;
ansz=(long double)totz/n;
SA();
printf("%.2Lf\n%.2Lf\n%.2Lf\n%.2Lf",ansx,ansy,ansz,ans);
}
```
此次比赛爆破了，但希望对大家有一点帮助。