Atcoder Beginner Contest 258 EX 题解
2022/7/13 23:25:25
本文主要是介绍Atcoder Beginner Contest 258 EX 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
这题有很高级的基于 \(Fibonacci\) 数列递推的做法,我提供一个简单做法。
那个高级做法的题解我附图在博客里面,不过禁止外传。
这个题矩阵加速的系数涉及到能不能选,按照不能选的数分段矩阵求幂是一个不错的方法
难度
差不多 \(2400\) 。
题意
给定 \(n,S\) 和一个数列 \(A\) ,已知数列 \(X\) 中每个数都是正奇数,所有数的和是 \(S\) ,任意一个前缀和不在数列 \(A\) 中,求这样的数列的个数。
$1\le n\le 1e5 $ \(1 \le S \le 1e18\) 。
题解
首先注意到一个比较 \(sb\) 的 \(DP\) ,设 \(f[i][j]\) 表示填了前 \(i\) 个数,和是 \(j\) 的方案数,复杂度很高,肯定不过。
考虑转化题意,题目限制了前缀和不能是 \(A\) 中的数,那我们考虑选前缀和来构成数列,那么限制就变成了不能选 \(A\) 中的数,然后就是,没有数的情况下和是 \(0\) ,整个数列选完了的情况下和是 \(S\) ,所以 \(0,S\) 必选。
因为所有数都是正奇数,那么前缀和肯定是奇数偶数交替出现的,所以相邻两个数必须奇偶性不同才是合法方案。
至此,我们巧妙地转化了题意与限制。
然后我们用一个 \(DP\) 来计数,设 \(dp[i][1/0]\) 表示已经填好了数列 \(X\) 中的某些数,最后填上的这个数和数字 \(i\) 的奇偶性是否相同。
转移方程:
\(dp[i][1]=dp[i-1][0]\) 。
\(dp[i][0]=dp[i-1][1]+dp[i-1][0]\) \(\times\) \([i不属于A]\) 。
大概解释一下,状态 \((i,1)\) 表示最后一个数和 \(i\) 奇偶性相同,那必然和 \(i-1\) 奇偶性不同,这个状态一定不会选进 \(i\) ,所以不担心 \(i\) 是否属于 \(A\) 。
状态 \((i,0)\) 就略显复杂,包含了部分不选 \(i\) 的情况,也即此处 \(dp[i-1][1]\) ,而选 \(i\) 则需要和上一个数奇偶性不同,也就是和 \(i-1\) 奇偶性相同,再注意一下 \(i\) 是不是在 \(A\) 中即可。
这个转移式,我觉得和 \(Fibonacci\) 数列有相似性,所以这个也是可以用矩阵加速的,每次求幂是 \(A_{i+1}-A_i-1\) 次,矩阵加速具体看我代码。
#include<bits/stdc++.h> #define N 100005 #define p 998244353 #define ll long long using namespace std; ll n,a[N],s; struct node { ll m[2][2]; }A,B,C; node mul(node a,node b) { node c; memset(c.m,0,sizeof(c.m)); for(int i=0;i<=1;i++) { for(int j=0;j<=1;j++) { for(int k=0;k<=1;k++) c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%p)%p; } } return c; } node ksm(node a,ll b) { node c; memset(c.m,0,sizeof(c.m)); for(int i=0;i<=1;i++) c.m[i][i]=1; while(b) { if(b&1) c=mul(c,a); a=mul(a,a); b=(b>>1); } return c; } int main() { scanf("%lld%lld",&n,&s); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); A.m[0][0]=1;A.m[0][1]=1;A.m[1][0]=1; B.m[0][1]=1;B.m[1][0]=1; C.m[0][0]=1; for(int i=0;i<=n-1;i++) { C=mul(C,ksm(A,a[i+1]-a[i]-1)); C=mul(C,B); } C=mul(C,ksm(A,s-a[n])); printf("%lld",C.m[0][1]); return 0; }
这篇关于Atcoder Beginner Contest 258 EX 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升