且高出的标价(即当天的股价与前一天的股价之差)不会超越M,股票每日的价格已知是正整数

尝试用Markdown写一篇博客
3142: [Hnoi2013]数列
Description
小T近日在学着买股票,他拿到内部音讯:F集团的股票将会疯涨。股票每一天的价格已知是正整数,并且鉴于客观上的原故,最七只好为N。在疯涨的K天中小T观察到:除第二天外每日的股价都比今日高,且高出的价格(即当天的股价与前一天的股价之差)不会超越M,M为正整数。并且这个参数知足M(K-1)<N。
小T忘记了那K天每一天的切切实实股价了,他今后想知道那K天的股价有微微种或许。
Input
唯有一行用空格隔开的多个数:N、K、M、P。对P的验证参见后边“输出格式”中对P的表明。
输入保险二成的数据M,N,K,P≤30000,保障百分之百的数据M,K,P≤10^9,N≤10^18 。
Output
仅包蕴一个数,表示这K天的股价的可能种数对于P的模值。
Sample Input
7 3 2 997
Sample Output
16

尝试用Markdown写一篇博客
3142: [Hnoi2013]数列
Description
小T近日在学着买股票,他取得内部音讯:F公司的股票将会疯涨。股票天天的价格已知是正整数,并且由于客观上的缘由,最三只好为N。在疯涨的K天中小T观察到:除第二天外天天的股价都比前些天高,且高出的价位(即当天的股价与前一天的股价之差)不会当先M,M为正整数。并且那个参数知足M(K-1)<N。
小T忘记了那K天每一天的切切实实股价了,他明日想领悟这K天的股价有稍许种或许。
Input
唯有一行用空格隔开的两个数:N、K、M、P。对P的辨证参见后边“输出格式”中对P的表达。
输入保障十分二的数据M,N,K,P≤30000,保障百分百的数据M,K,P≤10^9,N≤10^18 。
Output
仅包括3个数,表示那K天的股价的或是种数对于P的模值。
Sample Input
7 3 2 997
Sample Output
16

第③来讲讲自个儿是咋做(鬼)出那道题的。
没错就是打表。
对上次测验打完表没见到1,2,6,24是阶乘的事情时刻思念的自个儿控制用打表做出那道一看就是打表题的题。
第1自身花了20分钟庸庸碌碌,对于答案f(n,k,m)打了二个小表,什么都并未察觉。
20秒钟左右自身起来定点k和m,移动n。
实验了几组k在2~4的多少后意识从n到n+1,答案会增强m^(k-1)。
试到三十多分钟,计算出:规律是在n=m(k-1)处伊始的。

第三来讲讲自个儿是如何做(鬼)出那道题的。
没错就是打表。
对上次考试打完表没见到1,2,6,24是阶乘的事情朝思暮想的自个儿控制用打表做出那道一看就是打表题的题。
第三自个儿花了20分钟毫无作为,对于答案f(n,k,m)打了一个小表,什么都不曾察觉。
20分钟左右自个儿起来定点k和m,移动n。
实验了几组k在2~4的多寡后发现从n到n+1,答案会增进m^(k-1)。
试到27分钟,总括出:规律是在n=m(k-1)处起首的。

对!因为题材保障了n>m(k-1),所以那一个原理能够放心大胆用。

下一场自个儿打了关于k,m的f(m*(k-1),k,m)的表,即临界表。
约莫长这几个样子:

k\m     2     3     4     5
2       1     3     6     10
3       4     18    48    100
4       12    81    288   750
5       32    324   1536  5000

第1应声过去没什么规律?
乱搞到40分钟,发现第k行的都能被(k-1)整除,除掉再看:

k\m     2     3     4     5
2       1     3     6     10
3       2     9     24    50
4       4     27    96    250
5       8     81    384   1250

发觉每一列下来都以乘以m?所以一旦看率先列。

m     2     3     4     5
      1     3     6     10

相距是个等差数列,那就是个2回多项式了。
那会儿规律就相比较分明了:(m-1)*m/2。
然后再整理一下就会拿走答案:

对!因为难点保障了n>m(k-1),所以这几个规律可以放心大胆用。

下一场小编打了关于k,m的f(m*(k-1),k,m)的表,即临界表。
约莫长这几个样子:

k\m     2     3     4     5
2       1     3     6     10
3       4     18    48    100
4       12    81    288   750
5       32    324   1536  5000

首先随即过去没什么规律?
乱搞到40分钟,发现第k行的都能被(k-1)整除,除掉再看:

k\m     2     3     4     5
2       1     3     6     10
3       2     9     24    50
4       4     27    96    250
5       8     81    384   1250

发现每一列下来都以乘以m?所以只要看率先列。

m     2     3     4     5
      1     3     6     10

离开是个等差数列,那就是个贰回多项式了。
那会儿规律就比较显然了:(m-1)*m/2。
然后再整理一下就会获取答案:

Ans=(k-1)×(m-1)×m/2×m^(k-2)+[n-m(k-1)]×m^(k-1)

五十几分钟不到开打,一个钟头不到就做完了。
身处省选里面那一个时辰是足以接受的(NOIPT2也是1h左右呢?)。

本条时候我们无法满意是啊?要明白正解是什么样。
第①步:将原数组差分,得到k-贰个[1,m]内的正整数a[1…k-1]。
第3步:当前方案数即为n-sum(a[1] to a[k-1])。
故而总的方案数就是sum(n-sum(a[1] to a[k-1]))。
把n提出来,为n×m^(k-1)。
下一场前面那多少个东西,网上的精晓自身推不出来,是要对此各种东西单独考虑?不会。

Ans=(k-1)×(m-1)×m/2×m^(k-2)+[n-m(k-1)]×m^(k-1)

伍拾贰分钟不到开打,3个钟头不到就做完了。
座落省选里面这些日子是足以承受的(NOIPT2也是1h左右吗?)。

以此时候我们无法满足是啊?要理解正解是如何。
第2步:将原数组差分,得到k-3个[1,m]内的正整数a[1…k-1]。
第一步:当前方案数即为n-sum(a[1] to a[k-1])。
为此总的方案数就是sum(n-sum(a[1] to a[k-1]))。
把n提出来,为n×m^(k-1)。
然后前面那多少个东西,网上的了然作者推不出去,是要对此各个东西单独考虑?不会。

相关文章