[海军国际项目办公室]NOIP 2021

本文主要是介绍[海军国际项目办公室]NOIP 2021，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

NOIP 2021

题目概述

题解

这波直接未来题

我们可以先找到$p=4324321$的一个原根$G$，这样，每个数都可以用这个原根的次方表示出来，我们记$i=G^{a_i}$。
显然，如果$p$还有另外一个原根$G^{\prime }$，那么必然有$(G^{\prime },\phi (p)=p-1)=1$，只有这样才能让$G^{\prime }$的次方能够在$\phi (p)$内全部不同。
所以，我们只需要判断$a_i$是否与$\phi (p)$互质就可以知道它是不是原根。
不如直接将$\phi (p)$分解质因数，$\phi (p)=2^5\times 3^3\times 5\times 7\times 11\times 13$，可以直接判断是不是这$6$个数的倍数。

我们得到原根后考虑如何寻找我们的$k_i$。
显然有，$t_i\equiv k_i^{s_i}(\mathrm{m}\mathrm{o}\mathrm{d}p)\Rightarrow r^{a_{t_i}}\equiv r^{a_{k_i}{s}_i}(\mathrm{m}\mathrm{o}\mathrm{d}p)$
由于$r$是$p$的原根，所以我们可以转化到次数上的相等，这里该更换一下$k_i$与$t_i$的含义，于是有，
$$t_i\equiv k_i{s}_i(\mathrm{m}\mathrm{o}\mathrm{d}\phi (p))$$由于$s$在可见$\mathrm{A}\mathrm{S}\mathrm{C}\mathrm{I}\mathrm{I}$码中的范围大概只有$[32,126]$，我们可以按照$\mathrm{m}\mathrm{o}\mathrm{d}m$的余数给所有数分类，对于每一类，我们可以通过前面几个数找到有哪些可能的$k_i$，再通过后面的数去检验我们的$k_i$是否正确。
这样的时间复杂度大概是 $O\left(m|C|{\sum }_{i\in C}(p,i)\right)$，大概有$70pts$。

但事实上我们完全可以对其进行优化。
我们发现对于$c=32$(空格)这样数字，它刚好可以整除我们的$\phi (p)$，如果拿它去寻找我们可能的$l$，就只有$32$中可能，其中可以成为原根的更少。
类似的还有$\text{inhlucp}$这$7$个字符，总共有$8$个字符。
由于题目保证我们所选择文本都是 符合英语书写习惯的有意义的 文本，而且基本每个类都有$[40,50]$个字符，所以我们可以猜测我们这八个字符在每个类中都出现过。实际上仅仅是空格就在$99\%$的类里面出现过了。
这样的话我们就可以大幅的压缩我们枚举的可能的$k_i$的个数了。
求出$k_i$后除过去就可以得到我们的$s$了，毕竟$k_i$是与$\phi (p)$互质的。

时间复杂度$O\left(p+8n+117m\log \phi (p)\right)$。
实际上我们可以开始就用线性筛预处理每个数是不是我们的原根，而后面有时基本不可能枚举到我们的$u$的，所以实际上快得多。

源码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define MAXN 5000005
#define MAXM 100005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL;       
const int INF=0x3f3f3f3f;       
const int mo=4324321;
const int mod=4324320;
const int inv2=499122177;
const double jzm=0.997;
const int zero=10000;
const int orG=17;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<LL,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,LL s,int p){int t=1;while(s){if(s&1LL)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1LL;}return t;}
int n,m,taskid,a[MAXN],num[MAXN],ord[MAXN],tot,pw[MAXN],head[MAXM],nxt[MAXN],val[MAXN];
char ans[MAXN],key[10]={0,' ','i','n','h','l','u','c','p'};
vector<int>tmp;
bool range(int x){return 32<=x&&x<=126;}
signed main(){freopen("decrypt.in","r",stdin);freopen("decrypt.out","w",stdout);read(n);read(m);read(taskid);num[1]=0;int now=1;const int pG=928440;for(int i=1;i<mo-1;i++)now=1ll*now*orG%mo,num[now]=i,pw[i]=now;for(int i=1;i<=n;i++)read(a[i]),val[i]=num[a[i]],nxt[i]=head[i%m],head[i%m]=i;for(int i=0;i<m;i++){int typ=0,tid=0;tmp.clear();for(int k=1;k<=8&&!tid;k++)for(int j=head[i];j&&!tid;j=nxt[j])if(val[j]%key[k]==0)typ=val[j]/key[k],tid=k;for(int stp=mod/key[tid];typ<mod;typ+=stp)if((typ&1)&&(typ%3)&&(typ%5)&&(typ%7)&&(typ%11)&&(typ%13))tmp.pb(typ);int siz=tmp.size();for(int j=0;j<siz;j++){int x=tmp[j],ix=qkpow(x,pG-1,mod);bool flag=0;for(int k=head[i];k;k=nxt[k])if(!range(1ll*val[k]*ix%mod)){flag=1;break;}if(flag)continue;int st=i;if(!st)st=m;for(int k=head[i];k;k=nxt[k])ans[k]=1ll*val[k]*ix%mod;break;}}for(int i=1;i<=n;i++)putchar(ans[i]);puts("");return 0;
}

谢谢！！！

这篇关于[海军国际项目办公室]NOIP 2021的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---