P4925 [1007]Scarlet的字符串不可能这么可爱

    • 453通过
    • 2K提交
  • 题目提供者 Scarlet 芙兰朵露
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 字符串 状态压缩,状压
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Scarlet妄图构造字符集为$k$,长度为$L$的字符串,满足没有任何一个长度超过$1$的回文连续子串。

    看起来这样的字符串太多了,Scarlet随手加了个限制:她指定了字符串的第$s$位为$w$。

    这下Scarlet不会做了,请你来帮她计算究竟有多少满足条件的字符串。按照套路,你只要求出答案对$p$取模后的结果。

    输入输出格式

    输入格式:

    第一行三个整数$k,L$和$p$,分别表示构造的字符串的的字符集、长度和模数。

    第二行两个整数$s,w$,描述Scarlet给的限制。

    注意:$s=0$表示该数据点中Scarlet十分良心地没有添加限制

    输出格式:

    一行一个整数,表示答案对$p$的取模后的结果。

    输入输出样例

    输入样例#1: 复制
    3 3 233
    1 1
    输出样例#1: 复制
    2

    说明

    字符集:一个字符串中不同字符的数量。例如,字符集是3的话,你可以认为字符串仅由“A”、“B”、“C”三个字母组成。

    样例解释:第一个字符固定A,那么符合要求的字符串是ABC,ACB。而AAB字符串包括AA这个回文子串,ACA本身就是回文串,一次类推。

    对于50%的数据,$k\leq5,L\leq10$

    对于另30%的数据,$s=0$

    对于100%的数据$1\leq k,L\leq 10^{18},0\leq s\leq L,1\leq w\leq k,1\leq p\leq 10^9$

    标程展开

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。