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

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

NOIP 2021

题目概述

在这里插入图片描述

题解

~~这波直接未来题~~

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

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

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

时间复杂度 $O\left(p+8n+117m\log\varphi(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;
}