模模塔 （HG 2018.10.2 T3）

 考场上只想到了暴力。。 这道题很巧妙，采用分块的思想。 很容易可以知道，当i固定的时候且i/j不变时，j的取值是固定的。我们看一看bj，此时为以$\lfloor\frac{i}{j}\rfloor$公差的等差数列。 我们这时候可以预处理出一个前缀和，用sum[i][j]存从i开始往前公差为j的b的前缀和。然后，我们当$j\le \sqrt i$时，暴力枚举即可，当$j\ge \sqrt i$时就可以用sum数组来算了 ```cpp #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define int long long using namespace std; const int mod=123456789; int n,m,c[100100]; int a[100100],b[100100]; int sum[400][100100]; signed main() { scanf("%lld",&n);m=sqrt(n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=0;i<n;i++) scanf("%lld",&b[i]); for(int i=1;i<=m;i++) for(int j=0;j<n;j++) sum[i][j]=((j>=i?sum[i][j-i]:0)+b[j])%mod; for(int i=1;i<=n;i++) { for(int j=1;j<=min(m,i);j++) c[i]=(c[i]+a[i/j]*b[i%j])%mod; int l=m+1,r=m+1; while(l<=i) { int k=i/l;r=i/k;//这里是求i/j==k时，j的范围为[l,r] c[i]=(c[i]+a[k]*(sum[k][i-k*l]-(i>k*(r+1)?sum[k][i-k*(r+1)]:0)+mod))%mod; l=r+1; } } for(int i=1;i<=n;i++) printf("%lld\n",c[i]); return 0; } ```