noip模拟60 solutions
这个考试真的困，困死我了，导致我啥式子也推不出来
这次的题难到家啦，改题的时候一点思路也没有，只能一个字一个字的研究题解
不过战神是真的强，搞出来一个题解都搞不到的算法
T1 整除
题目挺善良的，直接把质因数分解给你了
但是我不会用啊
首先我们去看只有一个质因数的，这个需要保证\(x^m\equiv x(mod\ p)\)
这个的话你直接枚举就好了枚举每一个小于当前模数的数，直接快速幂判断
然后你发现这样之后，多个模数的时候仍然是要保证这个条件的
这个时候，你发现我可以对于每一个模数选出来一种同余方程，然后就组成了一个中国剩余定理
设每一个质因数的解有\(c_i\)个，这样的同余方程有\(\prod^{}_{}c_i\)
而每一个同余方程在\([0,n]\)范围内只有一个解，所以解的个数就是这么多种
直接枚举就好了，判断的时候用快速幂。。。
你发现好像过不了，但是你又发现好像只是求一个数的m次方，这个直接快速幂质数的，剩下的线性筛
AC_code
#include<bits/stdc++.h>
using namespace std;
#define oj
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int mod=998244353;
int T,c,m,ans,p;
int ksm(int x,int y){
int ret=1;
while(y){
if(y&1)ret=ret*x%p;
x=x*x%p;y>>=1;
}return ret;
}
int pw[10004],pr[10004],cnt;
bool vis[10004];
signed main(){
#ifdef oj
freopen("division.in","r",stdin);
freopen("division.out","w",stdout);
#endif
int id;scanf("%lld",&id);
scanf("%lld",&T);
while(T--){
ans=1;scanf("%lld%lld",&c,&m);
fo(i,1,c){
int res=0;scanf("%lld",&p);pw[1]=1;cnt=0;
fo(i,2,p-1){
if(!vis[i])pr[++cnt]=i,pw[i]=ksm(i,m);
for(int j=1;j<=cnt&&pr[j]*i<=p-1;j++){
pw[i*pr[j]]=pw[i]*pw[pr[j]]%p;
vis[i*pr[j]]=true;
if(i%pr[j]==0)break;
}
}
fo(i,1,p-1)vis[i]=false;
fo(i,1,p-1)if(pw[i]==i)res++;res++;
ans=ans*res%mod;
}
printf("%lld\n",ans);
}
}
上面那个太慢了，要跑三千多，下面推个式子。
你要解的方程是\(x^m\equiv x(mod\ p)\)，我们对他化简,设\(g\)是\(p\)的原根
\[g^{im}\equiv g^i(mod\ p) \] \[im\equiv i(mod \ p-1) \]上面那个东西在\([0,p-2]\)的范围内有\(\gcd(m-1,p-1)\)个解，因为
先移项
\[i(m-1)\equiv 0(mod\ p-1) \] \[p-1|i(m-1) \] \[\frac{p-1}{\gcd(m-1,p-1)}\mid i \]这个就很明显了吧，\(i\)在\(p-1\)范围内的解就是上面那个答案(战神的代码)
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int T,ans;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
signed main()
{
freopen("division.in","r",stdin);
freopen("division.out","w",stdout);
int id;scanf("%lld",&id);
scanf("%lld",&T);
while(T--)
{
int c,m,p;scanf("%lld%lld",&c,&m);ans=1;
for(int i=1;i<=c;i++)scanf("%lld",&p),ans=ans*(gcd(p-1,m-1)+1)%mod;
printf("%lld\n",ans);
}
return 0;
}
T2 糖果
就是数量很大嘛
但是你发现好像这个\(a\)是有循环节的啊
所以你理所当然的想到了矩阵快速幂，但是它复杂度炸了,虽然能过
所以正解是？？倍增\(DP\)
对于每一种\(a\)分别做一次，最后合并就行了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define oj
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=1e7+5;
const int M=105;
const int mod=998244353;
int n,m,a[N],A,B,P;
int pos[N],sum[M],dp[M][M][M],f[M][M][M],ans[M][M],tim[M];
int jc[M],inv[M];
int ksm(int x,int y){
int ret=1;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;y>>=1;
}return ret;
}
signed main(){
#ifdef oj
freopen("sugar.in","r",stdin);
freopen("sugar.out","w",stdout);
#endif
scanf("%lld%lld",&n,&m);
scanf("%lld%lld%lld%lld",&a[1],&A,&B,&P);
pos[a[1]]=1;
fo(i,2,n){
a[i]=(a[i-1]*A+B)%P+1;
if(pos[a[i]]){
int bas=(n-pos[a[i]]+1)/(i-pos[a[i]]);
int ys=(n-pos[a[i]]+1)%(i-pos[a[i]]);
fo(j,pos[a[i]],i-1){
if(a[j]>m)a[j]=m;
sum[a[j]]++;
}
fo(j,1,m)sum[j]*=bas;
fo(j,pos[a[i]],pos[a[i]]+ys-1)sum[a[j]]++;
fo(j,1,pos[a[i]]-1){
if(a[j]>m)a[j]=m;
sum[a[j]]++;
}
break;
}
pos[a[i]]=i;
}
if(a[1]>m||!sum[a[1]])
fo(i,1,n){
if(a[i]>m)a[i]=m;
sum[a[i]]++;
}
jc[0]=1;fo(i,1,m)jc[i]=jc[i-1]*i%mod;
inv[0]=1;inv[m]=ksm(jc[m],mod-2);
fu(i,m-1,1)inv[i]=inv[i+1]*(i+1)%mod;
fo(i,1,m){
if(!sum[i]){f[i][tim[i]][0]=1;continue;}
fo(j,0,i)dp[i][0][j]=1;
fo(l,1,60)fo(j,0,m)fo(k,0,j)dp[i][l][j]=(dp[i][l][j]+dp[i][l-1][j-k]*dp[i][l-1][k]%mod*jc[j]%mod*inv[j-k]%mod*inv[k])%mod;
int nn=sum[i];f[i][0][0]=1;
fu(l,60,0){
if((1ll<<l)>nn)continue;
nn-=(1ll<<l);tim[i]++;
fo(j,0,m)fo(k,0,j)f[i][tim[i]][j]=(f[i][tim[i]][j]+f[i][tim[i]-1][j-k]*dp[i][l][k]%mod*jc[j]%mod*inv[j-k]%mod*inv[k])%mod;
}
}
ans[0][0]=1;
fo(i,1,m)fo(j,0,m)fo(k,0,j)ans[i][j]=(ans[i][j]+ans[i-1][j-k]*f[i][tim[i]][k]%mod*jc[j]%mod*inv[j-k]%mod*inv[k])%mod;
printf("%lld",ans[m][m]);
}
T3 打字机
这个我不会，但是我A了,
不过这个\(DP\)确实玄学，
主要是理解数组是关于后缀定义的，并且你不确定转移某一位会不会造成贡献，所以两种转移是不一样的
AC_code
#include<bits/stdc++.h>
using namespace std;
#define oj
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=100005;
const int T=25;
char s[N],t[T];
int sn,tn,ad;
int m,l[N],r[N];
int dp[N][T][T*2];
signed main(){
#ifdef oj
freopen("print.in","r",stdin);
freopen("print.out","w",stdout);
#endif
scanf("%s",s+1);
scanf("%s",t+1);
sn=strlen(s+1);tn=strlen(t+1);
ad=tn+1;
memset(dp,0x3f,sizeof(dp));
fo(i,0,sn)fo(j,0,tn)fo(k,0,-j-1+ad)dp[i][j][k]=-1;
fo(k,ad,ad+tn)dp[0][0][k]=0;
fo(i,0,sn){
fo(j,0,tn){
fo(k,0,ad+tn){
if(i<sn)dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]+1);
if(j<tn)dp[i][j+1][k-1]=min(dp[i][j+1][k-1],dp[i][j][k]);
if(i<sn&&j<tn)dp[i+1][j+1][k+(s[i+1]==t[j+1])]=min(dp[i+1][j+1][k+(s[i+1]==t[j+1])],dp[i][j][k]+1);
}
}
}
scanf("%d",&m);
fo(i,1,m){
scanf("%d%d",&l[i],&r[i]);int pos;
fo(k,0,ad+tn)if(dp[r[i]][tn][k]>=r[i]-l[i]+1){pos=k;break;}
int ans=r[i]-l[i]+1-(pos-ad);
printf("%d\n",ans);
}
}