题目
题解
神奇题
定义题目要求的“合法序列”为 \(a_i \in [1,n],\; a_i+a_{i+1}\le a_{i+2}\)
定义长为l的斐波那契序列\(Fib_l\)为序列 \(\{fib_1,fib_2,\cdots, fib_l\}\)
定义两个数列的和为右对齐然后按位相加(不足补0),如 \(\{1,2,3\}+\{3,4\}=\{1,5,7\}\)
定义斐波那契序列组为若干斐波那契序列,如 \(\{\{1\},\{1,1,2\},\{1,1,2,3,5\}\}\)
重要结论:斐波那契序列组 与 合法序列 关于 \(\varphi=\)数列求和 构成双射
证明:
首先证明单射。反证,若不是单射,则存在两个斐波那契序列组S1,S2,二者和相同
记和的长度为l,因为长为l的斐波那契序列唯一,所以可以从S1,S2中提出相同数量的\(Fib_l\);如此类推,得S1=S2,矛盾
其次证明满射,任意一个合法序列都对应至少一个斐波那契序列组
记序列长度为l,则不断从合法序列中减去\(Fib_l\),则限制变为 \(a_i-fib_i+a_{i+1}-fib_{i+1}\le a_{i+2}-fib_{i+2}\) ,仍满足,因此减去之后仍是合法序列,直到全为0;此时就得到了一个斐波那契序列组
例子:\(\{1\}+\{1,1,2\}+\{1,1,2,3,5\}=\{1,1,3,4,8\}\)
因此问题变成了统计所有斐波那契序列组的答案,而斐波那契序列组又是若干斐波那契序列之和
设\(f_{l,i}\)表示长度最多为l,结尾为i的答案,每次往里面加一个\(Fib_l\)做完全背包即可
code
#include <bits/stdc++.h>
#define fo(a,b,c) for (int a=b; a<=c; a++)
#define fd(a,b,c) for (int a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%mod
#define mod 998244353
#define Mod 998244351
#define ll long long
#define file
using namespace std;
const int N=1e6+10;
int n,m,T;
ll f[N],ans;
int fib[31],prodfib[31];
void solve()
{
scanf("%d%d",&n,&m);
fib[1]=fib[2]=1;
prodfib[1]=prodfib[2]=m;
fo(i,3,30)
{
fib[i]=fib[i-1]+fib[i-2];
prodfib[i]=1ll*prodfib[i-1]*prodfib[i-2]%mod;
}
fo(i,2,30) prodfib[i]=1ll*prodfib[i-1]*prodfib[i]%mod;
f[0]=1;
fo(l,1,30)
{
fo(i,fib[l],n)
add(f[i],f[i-fib[l]]*prodfib[l]);
}
fo(i,1,n) add(ans,f[i]);
printf("%lld\n",(ans+mod)%mod);
}
int main()
{
// freopen("E.in","r",stdin);
T=1;
//scanf("%d",&T);
for (;T;--T) solve();
return 0;
}
标签:斐波,Triangle,prodfib,fib,序列,那契,Accepted,巅峰,mod
From: https://www.cnblogs.com/gmh77/p/18531011