首页 > 其他分享 >[ARC060F] Best Representation

[ARC060F] Best Representation

时间:2024-04-08 16:55:05浏览次数:23  
标签:le gcd 一个 text Period ARC060F Representation 整除 Best

题意

给定一个字符串 \(s\)。

设一个字符串 \(t\) 是好的,当且仅当不存在一个 \(\text{Period}\) 能整除 \(|t|\)。

求最小的划分段数使得每段都是好的,及最小的划分段数的方案数。

Sol

考虑两种特殊情况:

  • \(s\) 有长度为 \(1\) 的 \(\text{Period}\)。
  • \(s\) 本身就是好串。

前者答案显然为 \((n, 1)\),后者答案为 \((1, 1)\)。

集中注意力,不难想到一个结论:

最小的划分段数只会为 \(2\)。

显然可以考虑对于某个不好的串,可以考虑将她的最后一个字母割开。

注意到对于后面的这个串,我们一定可以找到某一个后缀串,可以使得她是好的串。

否则若 \(s\) 的所有后缀都是不好的串,那么 \(s\) 显然存在长度为 \(1\) 的 \(\text{Period}\)。

因此,证明该结论即证:对于所有的 \(s'\) 与 \(s' + c\) (\(c\) 为一个字符),两者不可能同为好串。

其实这个结论非常好证明。

首先,根据 \(\text{Periodicity Lemma}\) 可知:

若一个串有 \(\text{Period}\) \(p, q\),且 \(p + q \le |S| + \gcd(p, q)\),则 \(\gcd(p, q)\) 为该串的一个 \(\text{Period}\)。

显然,对于 \(s'\) 的整除 \(|s'|\) 的 \(\text{Period}\) \(x\),与 \(s' + c\) 的 \(\text{Period}\) \(y\)。

\(x \le \frac{|s'|}{2}\),\(y \le \frac{|s'| + 1}{2}\),所以 \(x + y \le |S| + \gcd(x, y)\)。

又因为 \(x\) 为 \(s'\) 的一个 \(\text{Period}\),所以 \(\gcd(x, y)\) 为 \(s'\) 的一个 \(\text{Period}\)。

显然 \(\gcd(x, y)\) 只能为 \(1\)。

对于长度为 \(1\) 的 \(\text{Period}\),已经被我们判过了。

所以结论成立。

对于第二问,考虑枚举每一个分割点,判断前后两段是否为好串即可。

根据 \(\text{Periodicity Lemma}\) 可知,直接判断最小 \(\text{Period}\) 是否整除即可。

标签:le,gcd,一个,text,Period,ARC060F,Representation,整除,Best
From: https://www.cnblogs.com/cxqghzj/p/18121717

相关文章

  • Domain Agnostic Learning with Disentangled Representations
    DomainAgnosticLearningwithDisentangledRepresentations1.Introduction本文研究了领域不可知论学习(DAL),这是一个比较困难但实际的问题,即知识从一个标记的源领域转移到多个未标记的目标领域。领域不可知学习的主要挑战是:(1)目标数据具有混合的领域,这阻碍了主流特征对齐......
  • [NSSRound#19 Basic]bestkasscn的超级简单密码
    题目:fromCrypto.Util.numberimport*importgmpy2fromfunctoolsimportreducefromsecretimportflagp=getPrime(1024)i=0whileTrue:r=p*5+iifisPrime(r):i=0breakelse:i+=1whileTrue:q=p*......
  • 解决主流办法没能HttpMediaTypeNotAcceptableException: No acceptable representatio
    问题描述:        写web项目时遇到一些小问题,前端请求后端死活报406错误问题,一些网络上主流的方法试过之后仍然无法解决问题。问题分析:        @RestController会在返回结果时直接返回对象,再由Spring将对象转为json,如果结果对象没有get方法,就会报以上错误......
  • Best AI Lead Generation Software Tools 2024
    Fromhttps://www.mapleadscraper.com/blog/best-ai-lead-generation-toolsExtractEmailsFromGoogleMapsWhyAILeadGenerationSoftwareisEssentialforYourBusinessMapLeadScraperhigh-qualityleadsiscrucialforbusinessestoclosedeals,increasereve......
  • 论文精读:When Noisy Labels Meet Long Tail Dilemmas A Representation Calibration M
    Introduction作者考虑了数据集常见的两个问题:1、部分数据被错误得标注;2、数据呈长尾分布。之前涌现了很多工作分别针对这两个问题,但当两者同时存在,它们不能很好的工作。专门针对噪声标签的方法,总是依赖于一些假设,但这些假设在long-tailed上不一定成立。例如利用memorizationeff......
  • The Best Car Diagnostic Tool Among Diagnostic and Testing Tools
    Inthismodernera,carshavebecomeanessentialpartofourlives.However,likeanyothermachine,theyarepronetobreakdownsandmalfunctions.Whenfacedwithcartroubles,itiscrucialtohavetherightdiagnosticandtestingtoolsatyourdisposa......
  • 《Decoupling Representation and Classifier for Long-Tailed Recognition》阅读笔记
    论文标题《DecouplingRepresentationandClassifierforLong-TailedRecognition》用于长尾识别的解耦表示和分类器作者BingyiKang、SainingXie、MarcusRohrbach、ZhichengYan、AlbertGordo、JiashiFeng和YannisKalantidis来自FacebookAI和新加坡国立大学......
  • CF1717E Madoka and The Best University
    CF1717EMadokaandTheBestUniversity简化题意求\(\sum\operatorname{lcm}(c,\gcd(a,b))\thinspace(a+b+c=n\thinspace,a,b,c\inZ^+)\)。做法由于我们只要知道其中两个数的值就能确定第三个数,所以只需要枚举两个数即可,这里考虑枚举\(c\)和\(a\)。设答案......
  • P2870 [USACO07DEC] Best Cow Line G
    https://www.luogu.com.cn/problem/P2870字典序最小显然贪心,若当前串首比串尾小,则取串首;若当前串首比串尾大,则取串尾。那串首串尾一样呢?这个顺序显然会影响到后续操作。考虑继续往内递归,如果碰到一样的,那么当前取什么都无所谓;若碰到不一样的,我们肯定是要取更小的那一边,因为这样......
  • 6-Nameless Representation of Terms
    无名称项deBruijn使用自然数来表示项,而不是字母组成的名称;自然数k表示绑定于第k个λ层的被界定的变量(thevariableboundbythek'thenclosingλ)马世龙版《类型和程序设计语言》使用“囿”来形容这种被界定的关系举例来说:λx.x表示为λ.0λx.λy.x(yx)表示......