在下的小博客

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$ 。

虽然证明繁杂,但代码还是很好打的,快速幂即可:

#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)$

代码很短:

#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$ ,高精岂不是太麻烦(毒瘤)?

我们有快速乘

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.分块可以过))

#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;
}

以下是线段树代码

#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 赛制的比赛中,退火等随机算法要慎用。

这题算法简单,就是随机一个坐标,更新一下最大值。

但怎么会这么简单?

我们首先来看一下复杂度:

我们先做一个试验:

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了一个点。

所以我希望大家认识到,退火算法虽好,但也需要优秀的调参,也要分析一下复杂度。

代码如下:

#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);
}

此次比赛爆破了,但希望对大家有一点帮助。