P5343 【XR-1】分块

    • 207通过
    • 1.4K提交
  • 题目提供者 xht37
  • 评测方式 云端评测
  • 标签
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    xht37 喜欢分块,以至于对一道不需要分块的题也要分块做。

    题目描述

    有一个长度为 $n$ 的序列,xht37 现在想分块维护它。

    PinkRabbit 要求他只准将序列分成 $PR$ 种长度的块。

    NaCly_Fish 要求他只准将序列分成 $NF$ 种长度的块。

    同一个人可能会要求 xht37 多次相同的块长。

    xht37 想同时满足 PinkRabbit 和 NaCly_Fish 要求,只好使用两个人都允许的长度分块。

    xht37 想知道,有多少种不同的分块方案,答案对 $10 ^ 9 + 7$ 取模。

    输入输出格式

    输入格式:

    第一行一个正整数 $n$,表示序列的长度。

    第二行一个正整数 $PR$,表示 PinkRabbit 要求的分块长度的种类数。

    第三行 $PR$ 个正整数,表示 PinkRabbit 要求的 $PR$ 种分块长度。

    第四行一个正整数 $NF$,表示 NaCly_Fish 要求的分块长度的种类数。

    第五行 $NF$ 个正整数,表示 NaCly_Fish 要求的 $NF$ 种分块长度。

    输出格式:

    输出一行一个整数,表示不同分块方案的种类数对 $10 ^ 9 + 7$ 取模的值。

    输入输出样例

    输入样例#1: 复制
    4
    3
    1 2 3
    3
    1 2 4
    输出样例#1: 复制
    5
    输入样例#2: 复制
    19260817
    7
    8 9 6 3 7 2 1
    7
    4 5 2 9 7 8 3
    输出样例#2: 复制
    859254329

    说明

    【样例 $1$ 说明】

    PinkRabbit 和 NaCly_Fish 都允许的块长为 $\{1,2\}$。

    长度为 $4$ 的序列分块,每块长度为 $\{1,2\}$ 的方案有:

    • $1\ 1\ 1\ 1$
    • $1\ 1\ 2$
    • $1\ 2\ 1$
    • $2\ 1\ 1$
    • $2\ 2$

    共 $5$ 种。

    【数据规模与约定】

    设最大块长为 $x$。

    对于 $60 \%$ 的数据,$1 \le n \le 10 ^ 6$,$1 \le PR,NF,x \le 10$,保证同一个人不会要求多次相同的块长。

    对于 $100 \%$ 的数据,$1 \le n \le 10 ^ {18}$,$1 \le PR,NF,x \le 100$。

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