题解：P10886 【MX-S3-T2】「FeOI Round 1」Journey

· · 题解

题目传送门：P10886 【MX-S3-T2】「FeOI Round 1」Journey。

思路

记 f_i 表示 i 的因数个数，可以用线性筛求出。

可以枚举 g_i 将题目转化成式子有多少个被计算到。

我们发现如果 a,b,c 能被计算到，当且仅当 a\le i,b> i,c|(i-a)，分情况讨论：

  1. 当 a<i 时，枚举 a 求 f_{i-a} 的和并将其记为 sum，那最后的贡献即为 sum\times (n+1-i)，但是现在求 sum 是 O(n) 的，因此需要使用前缀和优化。
  2. 当 a=i 时，c 可以任取，b 只要 \ge i 即可，这部分的贡献为 n\times (n+1-i)。

综上，每一个 g_i 的贡献就是 g_i(sum\times (n+1-i)+n\times (n+1-i))。

记得取模。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e7+10,mod=1e9+7;
int n,vis[N],pr[N],m,t,a[N],f[N],b[N];
inline void get(int n){
    f[1]=1;
    for (int i=2;i<=n;i++){
        if (!vis[i]) pr[++m]=i,a[i]=1,f[i]=2;
        for (int j=1;i*pr[j]<=n;j++){
            int x=i*pr[j];
            vis[x]=1;
            if (i%pr[j]==0){
                a[x]=a[i]+1,f[x]=f[i]/a[x]*(a[x]+1);
                break;
            } 
            else a[x]=1,f[x]=f[i]*2;
        }
    }
    for (int i=1;i<=n;i++) f[i]+=f[i-1];
}
inline int read(){
    char c=getchar();int f=1;int ans=0;
    while(c<48||c>57) (c==45?f=-1:1),c=getchar();
    while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
    return ans*f;
}
main(){
    int n=read(),A=read(),B=read(),C=read();b[n]=read();
    get(n);
    for (int i=n-1;i>0;i--)
        b[i]=(1ll*A*b[i+1]%mod*b[i+1]%mod+1ll*B*b[i+1]%mod+C)%mod;
    int ans=0;
    for (int i=1;i<=n;i++){
        int sum=0;
    //  for (int j=1;j<i;j++) sum=(sum+f[i-j])%mod;
        sum=f[i-1];
        ans=(1ll*b[i]*(n+1-i)%mod*sum%mod+ans+1ll*b[i]*n%mod*(n+1-i)%mod)%mod;
    }
    cout <<ans;
    return 0;
}