[杂题] HHHOJ#296. 「湖南省队集训2018 Day3」illustrious

出题人不知道干了什么 \(yy\) 出一个奇怪函数。打表可以发现,\(f(i)\) 等于 \(i\)\(f\) 中出现的次数。

\(g(n)\) 的意义是 \(1\)\(n\) 所有的数出现次数的和,也就是 \(f(i)=n\) 最大的 \(i\)

\(h\) 的式子里面的 \(g(f(n))-f(f(n))\) 是什么呢,结合 \(g\) 的意义,其实等于 \(g(f(n)-1)\)

相当于这个 \(h(n)\) 就是 \(\sum g(g(p))\)\(p\) 是小于 \(f(n)\) 的每种数出现的最后位置,还包括 \(n\) 这个位置。

现在问题就是怎么算 \(g(g(i))\) , 因为 \(g\) 是前缀和,差分一下发现: \[ g(g(i))-g(g(i-1))=f(i)i \\ g(g(i))=\sum_{j} f(j)j \] 暴力跳每种数就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int P=998244353,inv2=(P+1)/2;
int n,_test;
LL f[1000010],ans;
int main(){
f[1]=1; f[2]=2; for(int i=3;i<=1000000;i++) f[i]=f[i-f[f[i-1]]]+1;
scanf("%d",&_test);
while(_test--){
scanf("%d",&n);
LL now=1,gg=1,p=1; ans=1;
while(now+f[p+1]<=n){
p++;
(gg+=(now%P+1+now+f[p])%P*f[p]%P*inv2%P*p%P)%=P;
(ans+=gg)%=P; now+=f[p];
}
if(now<n){
p++;
(gg+=(now%P+1+n)%P*(n-now)%P*inv2%P*p)%P;
(ans+=gg)%P;
}
printf("%lld\n",(ans%P+P)%P);
}
return 0;
}