NOI.AC705 mmt

题意

对 $\forall i\in [1,n]$ ，求下式对 $123456789$ 取模的值

$$\sum_{j=1}^n a_{\lfloor \frac{i}{j} \rfloor}\times b_{i \ \mathrm{mod} \ j}$$

$n\le 10^5 \ , \ a_i,b_i\le 10^9$

题解

A了这题再随便打了下T3的暴力就rk18了。中途还突然把时限放宽到 $2s$ ，亏我卡了那么久的常数，最后还是在 $1s$ 内过去了。评测记录

原式可化为：

$$\sum_{j=1}^n a_{\lfloor \frac{i}{j} \rfloor} \times b_{i-\lfloor \frac{i}{j}\rfloor \times j}$$

可以对下标进行数值分块。令 $t=\lfloor \dfrac{i}{j} \rfloor$ ，则一个块内的权值即为：

$$a_t\times \sum_{k=l}^r b_{i-t\times k}$$

容易想到对 $b$ 作前缀和，但下标的公差 $t$ 不一定 $=1$ ，所以考虑维护差值不同的前缀和。

用 $sum[j][i]$ 表示当前为 $i$ ，差值为 $j$ 的前缀和，显然

$$sum[j][i]=sum[j][i-j]+b[i]$$

但空间不允许预处理出所有差值，通过玄学调参可以发现处理 $200$ 个左右是最优的，剩下的就暴力计算。

#include<bits/stdc++.h>
#define ha 123456789

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=100005;
int n,a[N],b[N],sum[205][N];

inline int _min(int x,int y) { return x<y ? x : y; }

inline int f(int k)
{
    int ans=0;
    for (int l=1,r,t;l<=k;l=r+1)
    {
        if ((t=k/l)!=0) r=_min(k/t,k);
        else r=k;
        if (t<=200) //用前缀和
        {
            if (k-t*r-t<0) ans=(ans+1ll*a[t]*sum[t][k-t*l]%ha)%ha;
            else ans=(ans+1ll*a[t]*(sum[t][k-t*l]-sum[t][k-t*r-t])%ha)%ha;
        }
        else //直接暴力计算
        {
            for (int i=l;i<=r;i++) ans=(ans+1ll*a[t]*b[k-t*i]%ha)%ha;
        }
    }
    return ans;
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=0;i<n;i++)
    {
        b[i]=read();
        for (int j=1;j<=200;j++)
        {
            if (i-j<0) sum[j][i]=b[i];
            else sum[j][i]=(sum[j][i-j]+b[i])%ha;
        }
    }
    for (int i=1;i<=n;i++) printf("%d\n",f(i));
    return 0;
}