#P6341. 生命的轨迹

    ID: 6426 传统题 1000ms 512MiB 尝试: 4 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-动态规划数位 DP计数 DP组合数学双射计数排序与序列处理滑动窗口滚动数组CF2600

生命的轨迹

生命的轨迹

题目描述

小 M 的实验室里有 n+mn+m 个活细胞,初始其中 nn 个细胞的活性系数为 xx,其余 mm 个的活性系数为 yy。

每秒选择当前的 kk 个细胞合并为一个新细胞,新细胞的活性系数等于这 kk 个细胞活性系数的算术平均数。保证这些细胞最终可以合并成一个细胞。

求最后一个细胞可能具有多少种不同的活性系数,答案对 109+710^9+7 取模。统计的是不同的最终数值,而不是合并方案数。

输入格式

从标准输入读入一行五个正整数 m,n,k,x,ym,n,k,x,y,含义如题目描述所示。注意前两个数的顺序是 m,nm,n。

输出格式

向标准输出输出一行一个整数,表示不同最终活性系数的个数,对 109+710^9+7 取模。

样例 1

2 2 2 9 8
5

样例 1 说明

五种可能的系数为 8.25,8.375,8.5,8.625,8.758.25,8.375,8.5,8.625,8.75。

样例 2

123 123 6 123 123
1

样例 2 说明

所有细胞初始活性系数都相同,任何合并都不会改变这个系数,因此答案为 11。

数据范围

对于 30%30\% 的数据,n,m,k≤15n,m,k\leq15。

对于全部数据,1≤n,m,k≤30001\leq n,m,k\leq3000,1≤x,y≤10181\leq x,y\leq10^{18},保证 (k−1)∣(n+m−1)(k-1)\mid(n+m-1),且最终能合并成一个细胞。由于 n,mn,m 均为正数且每次合并必须减少细胞数,实际合法输入须满足 k≥2k\geq2。