题目描述
The function $f$ is defined for all positive integers as follows:
$f(1)$ = $1$
$f(3)$ = $3$
$f(2n)$ = $f(n)$
$f(4n+1)$ = $2\cdot f(2n+1)-f(n)$
$f(4n+3)$ = $3\cdot f(2n+1)-2\cdot f(n)$
The function $S(n)$ is defined as $\sum_{i=1}^{n} f(i)$.
$S(8)=22$ and $S(100)=3604$.
Find $S(3^{37})$. Give the last $9$ digits of your answer.
题意
就是给你一个序列,问你这个序列的前缀和是多少
分析
显然是推公式嘛.
根据题意我们显然可以得到
$f(4n)+f(4n+1)+f(4n+2)+f(4n+3) = 6\cdot f(2n+1) - 2\cdot f(n)$ for $n\geq 1$
然后我们每四项加一下就可以得到下面这个公式
\begin{eqnarray}
S(4n+3) &=& \sum_{i=1}^{4i+3} f(i)\\
&=& 5 + \sum_{i=4}^{4i+3} f(i)\\
&=& 5 + \sum_{i=1}^{n} (6\cdot f(2i+1) - 2\cdot f(i))\\
&=& 5 + 6\sum_{i=1}^{n} (f(2i+1)+f(2i)) - 8\sum_{i=1}^{n} f(i)\\
&=& 5 + 6\sum_{i=2}^{2n+1} f(i) - 8\sum_{i=1}^{n} f(i)\\
&=& 5 - 6 + 6\sum{i=1}{2n+1} f(i) - 8\sum_{i=1}^{n} f(i)\\
&=& -1 + 6\sum{i=1}{2n+1} f(i) -8\sum_{i=1}^{n} f(i)\\
\end{eqnarray}
然后瞎搞就行了$\dots$
代码
给大佬递上我奇丑无比的代码 (/ω＼)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
38
39
using namespace std;
const int maxm = 1e7+10;
const int mod = 1e9;
inline int add(long long a,long long b){return (a+b)%mod;}
inline int mul(long long a,long long b){return a*b%mod;}
int num[maxm];
int sum[maxm];
long long f(long long a){
if(a<maxm&&num[a]) return num[a];
if(a==0) return 0;
if(a==1) return 1;
if(a==3) return 3;
if((a&1)^1) return f(a>>1);
else if((a&3)==3) return add(mul(3,f(a>>1)),mod-(f(a>>2)<<1));
else return add((f(a>>1|1)<<1),mod-f(a>>2));
}
long long S(long long a){
if(a<maxm) return sum[a];
long long ret = 0;
if(a%4==3){
ret = add(ret,mul(6,S(a>>1)));
ret = add(ret,mod-mul(8,S(a>>2)));
ret = add(ret,mod-1);
}else{
while(a%4!=3) ret = add(ret,mod-f(++a));
ret = add(ret,S(a));
}
return ret;
}
int main(){
for(int i = 1;i<maxm;i++) num[i] = f(i),sum[i] = add(sum[i-1],num[i]);
long long nouse = 1;
for(int i = 1;i<=37;i++){
nouse = (nouse<<2)-nouse;
}
cout<<S(nouse)<<endl;
return 0;
}
