P4491 [HAOI2018]染色

    • 394通过
    • 881提交
  • 题目提供者 panda_2134
  • 评测方式 云端评测
  • 标签 容斥 快速数论变换NTT 生成函数 各省省选 2018 河南 O2优化
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 512MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    HAOI2018 Round2 第二题

    题目描述

    为了报答小 C 的苹果, 小 G 打算送给热爱美术的小 C 一块画布, 这块画布可 以抽象为一个长度为 $N$ 的序列, 每个位置都可以被染成 $M$ 种颜色中的某一种.

    然而小 C 只关心序列的 $N$ 个位置中出现次数恰好为 $S$ 的颜色种数, 如果恰 好出现了 $S$ 次的颜色有 $K$ 种, 则小 C 会产生 $W_k$ 的愉悦度.

    小 C 希望知道对于所有可能的染色方案, 他能获得的愉悦度的和对 $1004535809$ 取模的结果是多少.

    输入输出格式

    输入格式:

    从标准输入读入数据. 第一行三个整数 $N, M, S$.

    接下来一行 $M + 1$ 个整数, 第 $i$ 个数表示 $W_{i-1}$ .

    输出格式:

    输出到标准输出中. 输出一个整数表示答案.

    输入输出样例

    输入样例#1: 复制
    8 8 3
    3999 8477 9694 8454 3308 8961 3018 2255 4910
    输出样例#1: 复制
    524070430
    输入样例#2: 复制
    见 https://www.luogu.org/paste/rxrv9utg
    输出样例#2: 复制
    231524284

    说明

    特殊性质: $\forall 1 \le i \le m, W_i = 0$

    对于 $100\%$ 的数据, 满足 $0 \le W_i < 1004535809$ Data

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