妙妙题。
题意
给定 \(F_0(x)=a_{(x-1)\bmod n +1}\)。
\[F_k(x)=F_{k-1}(x)-\sum\limits_{i=2}^n F_k(\lfloor\frac{n}{i}\rfloor)
\]
求 \(F_k(m)\)。
\(1\le n\le 10^4,1\le m\le 10^{10},1\le k\le 3\)。
直接数论分块求解的复杂度是 \(O(m^{\frac{3}{4}}k)\)，难以通过。
如果像杜教筛那样做到 \(O(m^{\frac{2}{3}}k)\) 的话就能通过。
关键在于如何快速求解 \(F_k(x),x\le m^{\frac{2}{3}}\)。
考虑杜教筛的逆过程，\(F\) 相当于杜教筛的前缀和函数，那么复原出原函数：
\[G_k(x)=F_k(x)-F_k(x-1)\\
=G_{k-1}(x)-\sum\limits_{i=2}^n F_k(\lfloor\frac{n}{i}\rfloor)-F_k(\lfloor\frac{n-1}{i}\rfloor)\\
=G_{k-1}(x)-\sum\limits_{i>1,i|n} F_k(\frac{n}{i})-F_k(\frac{n}{i}-1)\\
=G_{k-1}(x)-\sum\limits_{i>1,i|n} G_k(\frac{n}{i})\\
\]
这样，就可以 \(O(kB\ln B)\) 处理出 \(F_k(1\sim B)\)。
于是，复杂度为 \(O(kB\ln B+\frac{km}{\sqrt{B}})\)，取 \(B=10^6\) 即可通过。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e4+10,M=1e6+10,mod=23068673;
int his[4][M],n,k,a[N];
ll m;
int HIS[3][N];
int cnt;
ll num[N];
unordered_map<ll,int>trs;
int calc(int k,ll n){
if(!k)return a[(n-1)%(::n)+1];
if(n<M)return his[k][n];
int id=trs[n];
if(~HIS[k-1][id])return HIS[k-1][id];
ll ans=calc(k-1,n);
for(ll l=2,r;l<=n;l=r+1){
r=n/(n/l);
ans=ans-(r-l+1)*calc(k,n/l)%mod;
}
return HIS[k-1][id]=ans%mod;
}
void init(int m){
for(int i=1;i<=m;i++)his[0][i]=a[(i-1)%n+1];
for(int i=m;i>=1;i--)(his[0][i]+=mod-his[0][i-1])%=mod;
for(int t=1;t<=k;t++){
for(int i=1;i<=m;i++)his[t][i]=his[t-1][i];
for(int i=1;i<=m;i++){
for(int j=i+i;j<=m;j+=i){
(his[t][j]+=mod-his[t][i])%=mod;
}
}
}
for(int t=1;t<=k;t++){
for(int i=1;i<=m;i++){
(his[t][i]+=his[t][i-1])%=mod;
}
}
}
int main(){
freopen(".in","r",stdin);
//freopen(".out","w",stdout);
memset(HIS,-1,sizeof HIS);
scanf("%d%lld%d",&n,&m,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
init(M-1);
for(int i=1;m/i>=M;i++)num[++cnt]=m/i;
reverse(num+1,num+1+cnt);
for(int i=1;i<=cnt;i++)trs[num[i]]=i;
cout<<(calc(k,m)+mod)%mod;
return 0;
}