Atcoder TUPC 2023(東北大学プログラミングコンテスト 2023)E. And DNA(矩阵快速幂+拆位讨论)

2024-03-15 22:28

本文主要是介绍Atcoder TUPC 2023(東北大学プログラミングコンテスト 2023)E. And DNA(矩阵快速幂+拆位讨论),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

长为n(3<=n<=1e9)的数组,第i个数ai在[0,m](m<=1e9)之间

对于i∈[1,n],均满足a[i]+(a[i-1]&a[i+1])=m,求这样可能的数组的方案数

特别地,认为a[0]=a[n],a[n+1]=a[1],即这个数组是个环形的数组

思路来源

官方题解

题解

从末位考虑,

1. 如果m=0,只能全是0,方案数为1

2. 如果m=1,由于1+(1&1)=2,0+(0&x)=0,所以不能有三个1相邻,不能有两个0相邻

将相邻位的数字每两个看成一个点,即从01/10/11出发,

01可以转移到10或11,11可以转移到10,10只能转移到01,矩阵快速幂求出长为n的方案数

3. 如果m为>=2的偶数,考虑末位是1还是0,

①如果是1,只能是1+(1&1)=2,此时还给倒数第二位贡献了1,需要再递归求m/2-1的方案

②如果是0,只能是全0,需要再递归求m/2的方案

有f(m)=f(m/2)+f(m/2-1)

4. 如果m为>=3的奇数,末位只能是1,并且由于没有进位,可以分开来看

有f(m)=f(1)+f((m-1)/2)

代码

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
using namespace std;
typedef long long ll;
const int N=1e5+10,mod=998244353;
struct mat {static const int MAXN=3;ll c[MAXN][MAXN];int m, n;mat(){memset(c, 0, sizeof(c));m=n=MAXN;}mat(int a, int b) : m(a), n(b) {memset(c, 0, sizeof(c));}void clear(){memset(c, 0, sizeof(c));}mat operator * (const mat& temp) {mat ans(m, temp.n);for (int i = 0; i < m; i ++)for (int j = 0; j < temp.n; j ++){for (int k = 0; k < n; k ++){ans.c[i][j] += c[i][k] * temp.c[k][j];ans.c[i][j]%=mod;}}return ans;}mat operator ^(ll n){mat M(*this),ans(M.m, M.m);for (int i = 0; i < M.m; i ++)ans.c[i][i] = 1;while (n > 0) {if (n & 1) ans = ans * M;M = M * M;n >>= 1;}return ans;}
}b;
//01 10 11 没有相邻两个0或者三个1的方案数
int n,m,ans;
int sol(int m){if(m==0)return 1;//全0if(m==1)return ans;if(m%2==0)return (sol(m/2)+sol(m/2-1))%mod;//进位和不进位return 1ll*ans*sol(m/2)%mod;
}
int main(){scanf("%d%d",&n,&m);b.c[0][1]=b.c[0][2]=1;//01->10 01->11b.c[1][0]=1;//10->01b.c[2][1]=1;//11->10b=b^n;rep(i,0,2){ans=(ans+b.c[i][i])%mod;}printf("%d\n",sol(m));return 0;
}

这篇关于Atcoder TUPC 2023(東北大学プログラミングコンテスト 2023)E. And DNA(矩阵快速幂+拆位讨论)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/813446

相关文章

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

v0.dev快速开发

探索v0.dev:次世代开发者之利器 今之技艺日新月异,开发者之工具亦随之进步不辍。v0.dev者,新兴之开发者利器也,迅速引起众多开发者之瞩目。本文将引汝探究v0.dev之基本功能与优势,助汝速速上手,提升开发之效率。 何谓v0.dev? v0.dev者,现代化之开发者工具也,旨在简化并加速软件开发之过程。其集多种功能于一体,助开发者高效编写、测试及部署代码。无论汝为前端开发者、后端开发者

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

利用Django框架快速构建Web应用:从零到上线

随着互联网的发展,Web应用的需求日益增长,而Django作为一个高级的Python Web框架,以其强大的功能和灵活的架构,成为了众多开发者的选择。本文将指导你如何从零开始使用Django框架构建一个简单的Web应用,并将其部署到线上,让世界看到你的作品。 Django简介 Django是由Adrian Holovaty和Simon Willison于2005年开发的一个开源框架,旨在简

CentOs7上Mysql快速迁移脚本

因公司业务需要,对原来在/usr/local/mysql/data目录下的数据迁移到/data/local/mysql/mysqlData。 原因是系统盘太小,只有20G,几下就快满了。 参考过几篇文章,基于大神们的思路,我封装成了.sh脚本。 步骤如下: 1) 先修改好/etc/my.cnf,        ##[mysqld]       ##datadir=/data/loc

SAM2POINT:以zero-shot且快速的方式将任何 3D 视频分割为视频

摘要 我们介绍 SAM2POINT,这是一种采用 Segment Anything Model 2 (SAM 2) 进行零样本和快速 3D 分割的初步探索。 SAM2POINT 将任何 3D 数据解释为一系列多向视频,并利用 SAM 2 进行 3D 空间分割,无需进一步训练或 2D-3D 投影。 我们的框架支持各种提示类型,包括 3D 点、框和掩模,并且可以泛化到不同的场景,例如 3D 对象、室

HNU-2023电路与电子学-实验3

写在前面: 一、实验目的 1.了解简易模型机的内部结构和工作原理。 2.分析模型机的功能,设计 8 重 3-1 多路复用器。 3.分析模型机的功能,设计 8 重 2-1 多路复用器。 4.分析模型机的工作原理,设计模型机控制信号产生逻辑。 二、实验内容 1.用 VERILOG 语言设计模型机的 8 重 3-1 多路复用器; 2.用 VERILOG 语言设计模型机的 8 重 2-1 多