A. 整除
式子还没推出来，先鸽着..
B. 糖果
很显然的矩阵乘，但是学习了倍增 \(dp\).
令 \(g_{i,j}\) 表示在同一个 \(a_i\) 的大小下，选了前 \(2_i\) 种，占了 \(j\) 个位置的方案数.
转移方程：\(g_{i,j}=\sum\limits_{k=0}^{k<=j}g_{i-1,k}*g_{i-1,j-k}*C_j^k\)
后面的 \(C_j^k\) 可以理解为前面已经排好之后的可重排列数.
后面直接背包转移就可以了.
B_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
#define ll long long int
#define ull unsigned ll
#define lf double
#define lbt(x) (x&(-x))
#define mp(x,y) make_pair(x,y)
#define lb lower_bound
#define ub upper_bound
#define Fill(x,y) memset(x,y,sizeof x)
#define Copy(x,y) memcpy(x,y,sizeof x)
#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
inline ll read() {
ll res=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return cit?res:-res;
}
} using namespace BSS;
const ll M=107,mod=998244353;
ll m,n,A,B,P,cnt,len,tot,lg2;
ll vis[(int)1e7+21],num[(int)1e7+21];
ll tms[M],val[M],c2[M];
ll g[65][M],f[M][65][M],C[M][M],dp[M][M];
signed main(){
File(sugar);
n=read(),m=read(),num[1]=read(),A=read(),B=read(),P=read(),vis[num[1]]=1,lg2=log2(n)+1;
for(int i=0;i<=100;i++){
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
for(ll i=2;i<=n;i++){
num[i]=(num[i-1]*A%P+B)%P+1;
if(vis[num[i]]){ cnt=i-1,len=i-vis[num[i]]; break; }
vis[num[i]]=i;
}
if(!cnt) len=n,cnt=n;
for(int i=1;i<=cnt;i++) vis[num[i]]=0;
for(int i=1;i<=cnt-len;i++){
num[i]=min(num[i],m);
if(!vis[num[i]]) val[++tot]=num[i],vis[num[i]]=1;
tms[num[i]]++;
}
for(ll i=cnt-len+1;i<=cnt;i++){
num[i]=min(num[i],m);
if(!vis[num[i]]) val[++tot]=num[i],vis[num[i]]=1;
tms[num[i]]+=(n-(cnt-len))/len+((n-(cnt-len))%len>=i-(cnt-len));
}
for(int i=1;i<=m;i++){
f[i][0][0]=1;
if(!tms[i]) { f[i][0][0]=1; continue; }
Fill(g,0);
for(int j=0;j<=i;j++) g[0][j]=1;
for(int j=1;j<=lg2;j++)
for(int k=0;k<=m;k++)
for(int h=0;h<=k;h++)
g[j][k]=(g[j][k]+g[j-1][h]*g[j-1][k-h]%mod*C[k][h]%mod)%mod;
for(int j=0;j<=lg2;j++){
if(!((tms[i]>>j)&1)) continue;
c2[i]++;
for(int k=0;k<=m;k++)
for(int h=0;h<=k;h++){
f[i][c2[i]][k]=(f[i][c2[i]][k]+f[i][c2[i]-1][k-h]*g[j][h]%mod*C[k][h]%mod)%mod;
}
}
}
dp[0][0]=1;
for(int i=1;i<=m;i++){
for(int j=0;j<=m;j++)
for(int k=0;k<=j;k++){
dp[i][j]=(dp[i][j]+dp[i-1][j-k]*f[i][c2[i]][k]%mod*C[j][k]%mod)%mod;
}
}
printf("%lld\n",dp[m][m]%mod);
exit(0);
}
C. 打字机
这东西感觉很神仙.
在转移前缀的同时更新作为答案的后缀.
单调的性质感觉也很难发现.
找性质一定朝题目所求的靠拢.
另外，一般的 \(dp\) 都是设 \(f_x=y\) ，一般都是已知 \(x\) 求合法 \(y\).
然而这次我们逆着，设已知 \(y\)，寻找最优的 \(x\).
即 \(f_{i,j,k}\) 表示考虑了 \(S\) 长度为 \(i\) 的前缀，\(T\) 长度为 \(j\) 的前缀，最大的\(x\)使得 \(x-h(x)\le k\)，\(h*(x)\) 和题解说的一样.
转移方程：\(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]}+1)\)
但是转移时要用自己更新后面的，而不是用前面的更新自己，比较玄..
还有就是用 STL 偷懒不写负数会 T.
C_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
#define ll int
#define ull unsigned ll
#define lf double
#define lbt(x) (x&(-x))
#define mp(x,y) make_pair(x,y)
#define lb lower_bound
#define ub upper_bound
#define Fill(x,y) memset(x,y,sizeof x)
#define Copy(x,y) memcpy(x,y,sizeof x)
#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
inline ll read() {
ll res=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return cit?res:-res;
}
} using namespace BSS;
const ll N=1e5+21,M=23,inf=1e9;
char s[N],t[M];
ll ls,lt,ops,ans,add;
ll f[N][M][M<<1];
signed main(){
File(print);
scanf("%s",s+1),scanf("%s",t+1),ls=strlen(s+1),lt=strlen(t+1),ops=read(),add=lt+1;
Fill(f,0x3f);
for(int i=0;i<=ls;i++){
for(int j=0;j<=lt;j++)
for(int k=j;k<=lt;k++)
f[i][j][-1-k+add]=-1;
}
for(int i=0;i<=lt;i++) f[0][0][-1-i+add]=-1,f[0][0][i+add]=0;
for(int i=0;i<=ls;i++){
for(int j=0;j<=lt;j++)
for(int k=-lt-1;k<=lt;k++){
if(i<ls) f[i+1][j][k+add]=min(f[i+1][j][k+add],f[i][j][k+add]+1);
if(j<lt) f[i][j+1][k-1+add]=min(f[i][j+1][k-1+add],f[i][j][k+add]);
if(i<ls and j<lt) f[i+1][j+1][k+(s[i+1]==t[j+1])+add]=min(f[i+1][j+1][k+(s[i+1]==t[j+1])+add],f[i][j][k+add]+1);
}
}
ll l,r;
while(ops--){
l=read(),r=read();
for(int i=-lt-1;i<=lt;i++){
if(f[r][lt][i+add]>=r-l+1) { ans=r-l+1-i; break; }
}
puts("");
printf("%d\n",ans);
}
exit(0);
}