字符加密 Valentino 函数 （伪分治）

题面

$ solution: $

这一题重点不在字符串加密，而是我们最后的求值： $ K^{s}\mod M $ ( $ s\leq36^{100000} $ )

而我们发现它的指数十分巨大，但众所周知的指数不能直接取模，所以我们进行一些优化。

首先，我们 $ O(n) $ 走一遍字符串，求出它加密所需要的进制 $ p $ ，然后我们将 $ K^s $ 进行数位处理，发现我们最终要求的值就是（其中 $ i $ 是我们 $ s $ 的位数）：

$ \prod K^{a[i]\times p^{i-1}} $

然后我们发现我们的 $ p^{i-1} $ 部分仍然有可能溢出，但是如果我们将它换成：

$ \prod K^{a[i]\times p\times p\times p......\times p} $

然后不断将上述式子用快速幂求值即可（因为是底数所以取模没问题）（当然我们还可以先预处理一下 $ K^{p\times p\times p........\times p} $ 这个部分）

$ code: $

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define inf 0x7fffffff

#define rg register int

using namespace std;

int n,m,t;

ll k,a,ans;

int b[100005];

char c[100005];

inline int qr(){

	char ch;

	while((ch=getchar())<'0'||ch>'9');

	int res=ch^48;

	while((ch=getchar())>='0'&&ch<='9')

		res=res*10+(ch^48);

	return res;

}

inline ll fast(ll x,int y){//快速幂

	ll res=1;

	while(y){

		if(y&1)res=res*x%m;

		x=x*x%m; y>>=1;

	}return res;

}

int main(){

	//freopen("cipher.in","r",stdin);

	//freopen("cipher.out","w",stdout);

	k=qr(),m=qr();

    while(scanf("%s",c+1)!=EOF){

		n=strlen(c+1); t=0;

		for(rg i=1;i<=n;++i){

			if(c[i]>='0'&&c[i]<='9')b[i]=c[i]-'0';

			else b[i]=c[i]-'a'+10;

			t=max(t,b[i]+1);

		}

		a=k; ans=1;

		for(rg i=n;i;--i){

			ans=ans*fast(a,b[i])%m;

			a=fast(a,t);

		}printf("%lld\n",ans);

	}

	return 0;

}