2018HN省队集训题
题意:定义 ff 为哥布伦数列, g(n)=i=1nf(i)g(n)=\sum_{i=1}^{n}f(i)h(n)=h(g(f(n))f(f(n)))+g(g(n))h(n)=h(g(f(n))-f(f(n)))+g(g(n))
h(n)h(n) </br> 100分 需要一点小技巧 (#^.^#)

题目描述

众所周知, 小 ii 非常 illustriousillustrious, 因此他数学很强什么都很强ii 发现了几个奇妙的函数:

g(n)=i=1nf(i)g(n)=\sum_{i=1}^{n}f(i)h(n)=h(g(f(x))f(f(x)))+g(g(x))h(n)=h(g(f(x))-f(f(x)))+g(g(x))

由于小 ii 非常 illustriousillustrious, 所以他可以 11 秒内脑补出 h(n)h(n) 的值, 不过为了确保稳妥根本不需要,所以他希望你再计算一遍, 为了防止出现很长的数字导致眼花缭乱,你只需要输出结果对 998244353998244353 取模之后的结果

输入格式

第一行一个正整数 TT,表示数据组数。 接下来 TT 行每行一个正整数表示一组数据的 nn

输出格式

TT 行,每行一个非负整数,表示该组数据询问的 h(n)h(n)998244353998244353 取模之后的结果。

输入样例

5
5
50
500
500000
500000000

输出样例

50
40441
62542986
698264366
972430889

数据范围与约定

对于 10%10\% 的数据,有 对于 50%50\% 的数据,有 对于 100%100\% 的数据,有

Solution

考试的时候水了 5050 分,其实是偷偷塞到oeis找到了一条 g(g(n))g(g(n)) 类似定义数列的递推式qwq 然后拆分递推式,发现 g(g(n))g(g(n)) 可以很显然地 O(1)O(1) 算出......

也就是 Solution 最后 g(g(n))g(g(n)) 可以差分,非常好算。水50分~

正解也就是将 f(109)f(10^{9}) 的数通过 f(106)f(10^{6}) 确定,然后维护一下 g(g(n)), n=fg(g(n)),~n=f10910^{9} 内的数据很容易就能推出来了,就做好了。

题解:illustrious.pdf

Code

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
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define drep(i,a,b) for(re i=(a);i>=(b);--i)
const int p = 998244353, M = 5e5;
int f[M+2], s[M+2];
long long g[M+2];
inline void init(const int N) {
f[1]=1;
rep(i,2,N) f[i]=f[i-f[f[i-1]]]+1;
rep(i,1,N) g[i]=g[i-1]+f[i];
rep(i,1,N) s[i]=(s[i-1]+1ll*i*f[i]*(g[i]+g[i-1]+1)/2)%p;
}
inline int F(int x) { return x>M?lower_bound(g+1,g+M+1,x)-g:f[x];}
inline int GG(int x) {
int pos=upper_bound(g+1,g+M+1,x)-g-1;
return (s[pos]+1ll*(pos+1)*(g[pos]+1+x)*(x-g[pos])/2)%p;
}

int T, n;

int main() {
scanf("%d", &T);
init(M);
int res;
while(T--) {
scanf("%d", &n); res=0;
for(int i=n;i;i=g[F(i)-1]) {
res += GG(i);
if(res>=p) res-=p;
}
printf("%d\n", res);
}
}