#P7207. [2018西部多校]贱

    ID: 7008 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2200提高+/省选-贡献法插板法容斥原理阶乘逆元预处理排列数计算双射计数补集转化

[2018西部多校]贱

题目描述

有一排长度为 nn 的点,初始全为白色。对每个 1≤x≤n−k+11\le x\le n-k+1,有一次把区间 [x,x+k−1][x,x+k-1] 涂成黑色的操作。你需要以任意顺序各执行一次这些操作。

对于给定的操作顺序,第一次将所有点涂黑之后剩下的操作数,称为该顺序的手贱程度。求所有操作顺序的手贱程度之和,对 109+710^9+7 取模。

输入格式

一行两个整数 n,kn,k。

输出格式

一行一个整数,表示答案对 109+710^9+7 取模的结果。

样例 1

5 2
12

样例 2

100 50
400502129

数据范围与约定

站内输入满足 1≤k≤n1\le k\le n。

测试数据比例 附加限制
20% n≤1000n\le 1000
另外 30% k=2k=2,n≤106n\le 10^6
另外 50% 1000≤k≤n≤1051000\le k\le n\le 10^5

原稿在第一组将下界印为 0≤k0\le k。本题的涂色和首次完成条件以正长度为准,站内全部评测数据均满足这一点。

原 PDF 题面