「整除·糖果·打字機·堆」on 9.23
T1 整除
解題思路
答案就是 n 的每一個質因數的合法的答案數相乘（證明的話就。。。。）
但是複雜度顯然不允許（雖然我們可以給指數取模水過去）。。
可以用積性篩（線性篩）利用質數篩出 \(x^m\) 然後就可以計算答案了
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=60,mod=998244353;
int n,task,m,cnt,c,ans,T,pri[10010],res[10010],s[N];
bool vis[10010];
int exgcd(int a,int b,int &x,int &y)
{
if(!b) return x=1,y=0,a;
int d=exgcd(b,a%b,x,y);
int z=y; x=y; y=z-(a/b)*y;
return d;
}
int power(int x,int y,int p=mod)
{
int temp=1; y%=p-1;
while(y)
{
if(y&1) temp=temp*x%p;
x=x*x%p; y>>=1;
}
return temp;
}
void solve()
{
c=read(); m=read(); ans=1;
for(int i=1;i<=c;i++) s[i]=read();
for(int i=1;i<=c;i++)
{
int sum=0;
for(int j=1;j<=s[i];j++)
if(vis[j]) res[j]=0;
else res[j]=power(j,m,s[i])%s[i];
for(int j=1;j<=s[i];j++)
{
if(res[j]==j%s[i]) sum++;
for(int k=1;k<=cnt&&pri[k]*j<=s[i];k++)
{
res[pri[k]*j]=res[pri[k]]*res[j]%s[i];
if(j%pri[k]==0) break;
}
}
ans=ans*sum%mod;
}
printf("%lld\n",ans);
}
void init()
{
for(int i=2;i<=10000;i++)
{
if(!vis[i]) pri[++cnt]=i;
for(int j=1;j<=cnt&&pri[j]*i<=10000;j++)
vis[i*pri[j]]=true;
}
}
signed main()
{
freopen("division.in","r",stdin); freopen("division.out","w",stdout);
init(); task=read(); T=read(); while(T--) solve();
return 0;
}
T2 糖果
倍增 DP 。。
不難發現資料都是有周期的并且大于 \(m\) 的糖果可以直接視為隻有 \(m\) 個。
然後我們就可以快速算出每一個數量的糖果的種類數了，然後進行倍增 DP。
設 \(g(i,j)\) 表示前 \(2^i\) 種糖果占 \(j\) 個位置的方案數：
\[g(i,j)=\sum\limits_{k=0}^jg(i-1,k)\times g(i-1,j-k)\times\binom{j}{k}
\]
然後對于相同數量的糖果我們所需要的種類數是一定了，是以用一個類似于上面的柿子加上背包的思想合并起來。
最後 DP 統計答案就好了
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e7+10,M=110,Lg=70,mod=998244353;
unordered_map<int,int> mp;
int T,s[N],n,m,a,b,p,las,maxn,p2[Lg],fac[M],ifac[M],cnt[N],ans[M][M],f[M][Lg][M],g[M][Lg][M],dep[M];
int power(int x,int y,int p=mod){int temp=1;while(y){if(y&1) temp=temp*x%p;x=x*x%p; y>>=1;}return temp;}
int C(int x,int y){return fac[x]*ifac[x-y]%mod*ifac[y]%mod;}
void solve(int lim)
{
for(int i=0;i<=lim;i++) f[lim][0][i]=1;
for(int i=1;i<=60;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=j;k++)
f[lim][i][j]=(f[lim][i][j]+f[lim][i-1][k]*f[lim][i-1][j-k]%mod*C(j,k))%mod;
int pos=lim; lim=cnt[pos]; g[pos][0][0]=1;
for(int i=60;i>=0;i--)
{
if(p2[i]>lim) continue; lim-=p2[i]; dep[pos]++;
for(int j=0;j<=m;j++)
for(int k=0;k<=j;k++)
g[pos][dep[pos]][j]=(g[pos][dep[pos]][j]+g[pos][dep[pos]-1][k]*f[pos][i][j-k]%mod*C(j,k))%mod;
}
}
signed main()
{
freopen("sugar.in","r",stdin); freopen("sugar.out","w",stdout);
n=read(); m=read(); maxn=s[1]=read(); a=read(); b=read(); p=read();
mp.insert(make_pair(s[1],1));
p2[0]=1; for(int i=1;i<=60;i++) p2[i]=p2[i-1]*2;
fac[0]=ifac[0]=1; for(int i=1;i<=m;i++) fac[i]=fac[i-1]*i%mod;
ifac[m]=power(fac[m],mod-2); for(int i=m-1;i>=1;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
for(int i=2;i<=n;i++)
{
s[i]=(s[i-1]*a+b)%p+1; maxn=max(maxn,s[i]);
if(mp.find(s[i])!=mp.end())
{
las=mp.find(s[i])->second;
T=i-las; break;
}
mp.insert(make_pair(s[i],i));
}
if(!las) las=n+1; maxn=min(maxn,m);
for(int i=1;i<las;i++) cnt[min(m,s[i])]++;
if(T) for(int i=las;i<=las+T-1;i++) cnt[min(m,s[i])]+=(n-i)/T+1;
for(int i=1;i<=m;i++)
if(cnt[i]) solve(i);
else g[i][dep[i]][0]=1;
ans[0][0]=1;
for(int i=1;i<=maxn;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=j;k++)
ans[i][j]=(ans[i][j]+ans[i-1][j-k]*g[i][dep[i]][k]%mod*C(j,k))%mod;
printf("%lld",ans[maxn][m]);
return 0;
}
T3 打字機
和題解的方法一樣，對于字首維護字尾的 \(h(i)\) 表示 \(S\) 長度為 \(i\) 的字尾和 \(T\) 的編輯距離。
那麼 \(f(i,j,k)\) 表示考慮了 \(S\) 長度為 \(i\) 的字首， \(T\) 長度為 \(j\) 的字尾，最大的 \(x\) 使得 \(x-h(x)\le k\)。
于是可以得到 DP 方程：
\[f(i,j,k)=min\{f(i-1,j,k)+1,f(i,j-1,k+1),f(i-1,j-1,k[S-i=T_j])\}
#include<bits/stdc++.h>
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e5+10,M=22,base=20;
int T,n,m,l,r,len,f[N][M][M<<1];
char s[N],t[M];
void init()
{
memset(f,0x3f,sizeof(f));
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
fill(f[i][j]-m-1+base,f[i][j]+base-j-1+1,-1);
for(int i=base-m-1;i<=base+m;i++) f[0][0][i]=min(f[0][0][i],0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=base-m-1;k<=base+m;k++)
f[i][j][k]=min(f[i][j][k],min(f[i-1][j][k]+1,min(f[i][j-1][k+1],f[i-1][j-1][k-(s[i]==t[j])]+1)));
}
int solve()
{
l=read(); r=read(); len=r-l+1;
return len-(lower_bound(f[r][m]+base-m,f[r][m]+base+m+1,len)-f[r][m])+base;
}
signed main()
{
freopen("print.in","r",stdin); freopen("print.out","w",stdout);
scanf("%s%s",s+1,t+1); n=strlen(s+1); m=strlen(t+1);
init(); T=read(); while(T--) printf("%d\n",solve());
return 0;
}