Modular Sequence

时间：2024-02-20 16:35:04浏览次数：15

这个题目的官方题解写的挺好的

写成这个样子我们就可以想到先把所有数都模一个$y$

然后我们就要考虑怎么构造这个数列了，注意这都已经是E了，一般是不会再出现像前面几道题目的直接构造了，一般是要利用算法了

这里我们就考虑怎么样才能够构造出来类似的数列。对任意一种方案，我们把只有单个$0$的blocks全部放到序列最后，我们现在就只需要决定最开始的一连串$b_1+k_1$到哪里就行了（也就是$k_1$的大小），只要我们前面决定了，我们只用判断剩下的位数是否存在一种合法的方案，最后填写出来符合题意的解

这个时候就要利用DP

其实就是考虑当前数值$s$，如果用上面说的$0\: 1 \: 2...\: 0 \: 1\: 2...$这种形式来填，最少会用多少个数

如果最少的都不行了，那么肯定就不行了；如果最少的可以，那么就存在一种方案了

但是这道题目记得特殊判断$n=1$的情况，然后还要记得不要用乘法判断，会溢出，把乘法换成除法

标签：...,题目,Sequence,Modular,最少,我们
From： https://www.cnblogs.com/dingxingdi/p/18023415

P4552 [Poetize6] IncDec Sequence
先看题目，因为在文中可以发现，它有一个区间加区间减的操作，所以我们想到了线段树和差分，而下面题目是要我们自己查找让所有的数字相同的最小步数。因此我们可以将线段树排除，那么来看差分，对于差分而言，所有的数字都相同，就可以看作对于所有的$2\lei\len$而言，$a_i=0$，最后的结果是......
《SagDRE: Sequence-Aware Graph-Based Document-Level Relation Extraction with Ada
代码原文地址关键参考文献：Document-LevelRelationExtractionwithAdaptiveThresholdingand LocalizedContextPooling摘要关系抽取（RE）是许多自然语言处理应用的重要任务，它的目标是从文档中抽取出实体之间的关系。文档级RE任务面临着许多挑战，因为它不仅需要跨句子......
CF1928E Modular Sequence
原题链接设$p=x\bmody$。思考发现本质是$x,x+y,x+2y,\cdots,x+k_1y,p,p+y,p+2y,\cdots,p+k_2y,p,p+y,p+2y,\cdots,p+k_3y\cdots$，即每次二操作会使$y$的系数变为$0$。枚举第$i$次操作是第一次二操作，记\(s_1=s-(i\timesx+y\times\dfrac{i(i-1)}{2}+(n-i)\time......
AT_abc270_g [ABC270G] Sequence in mod P 题解
题目传送门前置知识大步小步算法解法递推式为$x_{n}=(ax_{n-1}+b)\bmodp$，发现可以统一消去$\bmodp$，只在最后参与计算。以下过程省去模运算。当$x_{0}=t$时，则$n=0$即为所求。当$a=0,x_{0}\net$时，递推式转化为$x_{n}=b\bmodp$。若$b=t$，则......
CF1922E Increasing Subsequences 题解
解题思路因为可以有空集，那么我们首先构造第一段最长的连续上升的序列，那么这段序列中共有$2^{\mids\mid}$个上升子序列。接下来我们考虑补全剩余的，我们不妨将剩余的部分全部设为连续不增序列，那么设当前位置在第一段中有$k$个小于它的，那么添加这个数后可以增加\(2^{k-1}......
ABC240Ex Sequence of Substrings
题意简述有长度为$n$的01串，你现在要选出$k$个两两无交子串，使得将$k$个子串按照出现位置排序后，后者的字典序严格比前者大。最大化$k$。$\bm{n\le2\times10^4}$。分析首先的首先观察数据范围可知此题应该是个线性根号对数的时间复杂度首先有个显然的\(O(n......
[AGC024E] Sequence Growing Hard 题解
题目链接点击打开链接题目解法考虑如何添加数，使得$\{a_1,...,a_i\}$到$\{a_1,...,x,a_j,...,a_i\}$是合法的需要手玩一会才能发现合法条件很简单：$x>a_j$考虑对这个进行计数一个一个添元素是难维护的，现在假设有最终的序列，每个位置有$(v,dfn)$，分别为值和添加的次......
CF1924D Balanced Subsequences
题意简述有$n$个左括号和$m$个右括号，求最长合法括号子序列长度为$2k$的括号序列的数量，对$10^9+7$取模。多组数据。$T\le3\times10^3,n,m,k\le2\times10^3$分析可能需要的前置知识：如何求一个字符串的最长合法括号子序列？维护一个括号栈，若遇到左括号则直接......
CodeForces 1924D Balanced Subsequences
洛谷传送门CF传送门发现去掉匹配的$2k$个括号后，剩下的串一定形如$))\ldots)((\ldots($，其中右括号数量为$a=m-k$，左括号数量为$b=n-k$。考虑把剩下的串像$))\ldots)\mid((\ldots($一样分成两半。枚举左半边加入了$\frac{i}{2}$对匹配，则......
[ARC170C] Prefix Mex Sequence
给定$n,m,S_1\simS_n$，当$S_i=0$时$A_i\neq\mathrm{mex}(A_1\simA_{i-1})$，反之$A_i=\mathrm{mex}(A_1\simA_{i-1})$，求值域为$[0,m]$的$A$的数量$\bmod\998244353$。$1\len\le5000,0\lem\le10^9$。看到题目就会想到......

Modular Sequence

相关文章

赞助商

阅读排行