首页 > 其他分享 >Accepted极限代码巅峰赛 E Triangle

Accepted极限代码巅峰赛 E Triangle

时间:2024-11-06 21:00:38浏览次数:1  
标签:斐波 Triangle prodfib fib 序列 那契 Accepted 巅峰 mod

题目


题解

神奇题

定义题目要求的“合法序列”为 \(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

相关文章

  • 销售精英必备:五大实战策略,重塑职场心态,迈向成功巅峰
    销售是一项充满挑战与高标准要求的职业。为了取得卓越的销售业绩,销售人员必须具备良好的抗压能力,并能灵活调整工作心态,以积极且感恩的态度去面对职场与生活的种种。以下是提升销售人员心态的五大实用策略:放下无谓的面子观历史告诉我们,过分在意面子往往限制了个人的成长与成功。......
  • 数字时代的领航者,不容错过的巅峰盛会——The Open Group 2024大会盛情邀约
    随着全球数字化革命的深入推进,企业正面临着前所未有的挑战和机遇。如何在激烈的市场竞争中脱颖而出,实现可持续发展,已成为各行业领袖和专业人士共同关注的焦点。TheOpenGroup2024生态系统架构·可持续发展年度大会即将隆重举行,汇聚全球顶尖专家和业界翘楚,为您揭示数字化转型......
  • 超越OpenAI GPT-4o,Yi-Lightning指南:中国AI大模型新巅峰
    Yi-Lightning是零一万物公司最新发布的旗舰模型,它在国际权威盲测榜单LMSYS上超越了硅谷知名OpenAIGPT-4o-2024-05-13、AnthropicClaude3.5Sonnet,排名世界第六,中国第一,这标志着中国大模型首次实现超越OpenAIGPT-4o的成绩。Yi-Lightning在排行榜上的一些关键指标和......
  • 【Midjourney 中文版】AI 绘画新巅峰
    在当今数字艺术的璀璨星空中,Midjourney中文版如同一颗耀眼的新星,散发着独特而迷人的光芒。它是一款强大的人工智能绘画工具,将艺术与科技完美融合,为创作者们带来前所未有的创作体验。Midjourney中文版以其卓越的智能创作能力令人惊叹。只需用中文输入你心中的画面描述,无论是......
  • TypeError: add_triangle_mesh(): incompatible function arguments. The following a
    12024.10.1214:52Traceback(mostrecentcalllast):File"terrain_creation.py",line119,in<module>gym.add_triangle_mesh(sim,vertices.flatten(),triangles.flatten(),tm_params)TypeError:add_triangle_mesh():incompatiblefunct......
  • 2024 第七届“巅峰极客”网络安全技能挑战赛初赛 wp
    WEBEncirclingGame题目描述:Asimplegame,enjoyitandgettheflagwhenyoucompleteit.开题,前端小游戏,红点出不去就行直接玩通关了看看如何不玩也能拿到flag,flag存储在后端php文件内,前端找不到。看一下游戏的请求包,里面记录了红点的最后位置和防火墙(黑点)的位置。那么我们伪......
  • 洛谷题单指南-分治与倍增-P6648 [CCC2019] Triangle: The Data Structure
    原题链接:https://www.luogu.com.cn/problem/P6648题意解读:在一个n行的数字三角形中,求所有边长为k的正三角形最大值之和。解题思路:1、枚举法枚举每一个边长为k的三角形,在其中求max,然后累加,n最多3000,时间复杂度是n^4,显然超时。2、倍增和ST思想此题非常类似于RMQ问题,也就是求区......
  • 逆风飞驰·剑指巅峰|量子膜中国行新疆站圆满收官!
    秋天的阿勒泰千万不能错过?金秋九月,量子®膜踏上北疆游、和阿勒泰来了一场双向奔赴!逆风飞驰,不可限量,不断开拓的量子®膜开启中国行第一站——新疆,我们来了!DAY1北疆之旅拉开帷幕收拾行囊,整装待发!行程第一天,量子®膜团队在乌鲁木齐集结完毕,驾车前往阿勒泰,面对北疆这片充满魔力的风景......
  • 【艾思科蓝】前端框架巅峰对决:React、Vue与Angular的全面解析与实战指南
    【JPCS独立出版】​第三届能源与动力工程国际学术会议(EPE2024)_艾思科蓝_学术一站式服务平台更多学术会议请看:https://ais.cn/u/nuyAF3 引言在快速发展的前端技术领域,选择合适的框架或库对于项目的成功至关重要。React、Vue和Angular作为当前最流行的三大前端框架/库,各自......
  • 【洛谷 P1216】[USACO1.5] [IOI1994]数字三角形 Number Triangles 题解(动态规划)
    [USACO1.5][IOI1994]数字三角形NumberTriangles题目描述观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。在上面的样例中,从的路径产生了最大权值。输入格式第一个行一个正整数......