开发笔记:9.10模拟赛

#include
#define ri register int
using namespace std;
typedef long long ll;
const int N=100000+3;
const int M=320;
const int mod=123456789;
ll a[N],b[N],c[N];
int n,m;
ll f[N][M];
int main(){
scanf("%d",&n);
for(ri i=1;i<=n;i++)scanf("%d",&a[i]);
for(ri i=1;i<=n;i++)scanf("%d",&b[i-1]);
for(ri i=0;i<=n-1;i++){
for(ri j=1;j<=318;j++){
if(i-j>=0) f[i][j]=(f[i-j][j]+b[i])>=mod?f[i-j][j]+b[i]-mod:f[i-j][j]+b[i];
else f[i][j]=b[i];
}
}
for(ri i=1;i<=n;i++){
//cout<<"iiii "<
int j;
for(j=1;j*j<=i;j++){
(c[i]+=a[i/j]*b[i-(i/j)*j])%=mod;
}
//cout<<" before "<
int las=j-1;
for(ri an=i/j;an;an--){
//cout<<" an "<
int mx=i/an;
int len=mx-las;
//cout< //cout<
(c[i]+=a[an]*(f[i-an*(las+1)][an]-((i-an*(mx+1)>=0)?f[i-an*(mx+1)][an]:0)))%=mod;
las=mx;
}
printf("%d
",c[i]);
}
// for(int i=1;i<=n;i++)
return 0;
}

#include<iostream>
#include
#include
#include
#include
#include
#define ri register int
#define numb ch-‘0‘
using namespace std;
typedef long long ll;
typedef unsigned long long ui;
//typedef register int ri;
const int N=200000+5;
const int M=100000+5;
const int P=31;
ui mi[N];
ui h1[N];
ui h2[M];
char s1[N],s2[M];
int n,m;
int k;
int ans;
int main()
{
//freopen("mo.in","r",stdin);
//freopen("mo.out","w",stdout);
scanf("%s",s1+1);
scanf("%s",s2+1);
n=strlen(s1+1);
m=strlen(s2+1);
scanf("%d",&k);
mi[0]=1;
int up=max(n,m);

if(up<=1005){
for(int i=1;i<=n-m+1;i++){
int cnt=0;
int r=i;
for(int j=1;j<=m;j++){
if(s1[r]!=s2[j]) cnt++;
r++;
if(cnt>k) break;
}
//cout<
if(cnt<=k) ans++;
}
printf("%d",ans);
return 0;
}

for(int i=1;i<=up;i++){
mi[i]=mi[i-1]*P;
}
for(int i=1;i<=n;i++){
h1[i]=h1[i-1]*P+s1[i]-‘a‘;
}
for(int j=1;j<=m;j++){
h2[j]=h2[j-1]*P+s2[j]-‘a‘;
}
for(int i=1;i<=n-m+1;i++){
//cout<<" iii "<
int cnt=0;
int l1=i,l2=1,r1=i+m-1,r2=m;
while(cnt<=k&&l1<=i+m-1){
if(s1[l1]!=s2[l2]){
l1++;l2++;
cnt++;
}
else{
int L=l1,R=r1;
int mx=l1-1;
while(L<=R){
int mid=(L+R)>>1;
int an=mid-i+1;
ui hsh1=h1[mid]-h1[l1-1]*mi[mid-l1+1];
ui hsh2=h2[an]-h2[l2-1]*mi[an-l2+1];
if(hsh1==hsh2){
mx=mid,L=mid+1;
}
else R=mid-1;
}

if(mx==r1){
break;
}
else{
cnt++;
l1=mx+2;
l2=mx-i+3;
}
}
//cout<<" l1 "<
}
//cout<
if(cnt<=k){
ans++;
}
}
printf("%d",ans);
return 0;
}