且高出的价位(即当天的股价与前一天的股价之差)不会当先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的解释。
输入有限支持20%的数据M,N,K,P≤20000,保障100%的数据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的解释。
输入有限辅助20%的数据M,N,K,P≤20000,保险100%的数据M,K,P≤10^9,N≤10^18 。
Output
仅包涵一个数,表示那K天的股价的也许种数对于P的模值。
Sample Input
7 3 2 997
Sample Output
16

先是来讲讲我是咋办(鬼)出那道题的。
没错就是打表。
对上次考试打完表没看出1,2,6,24是阶乘的政工言犹在耳的我决定用打表做出那道一看就是打表题的题。
首先自己花了20分钟毫无作为,对于答案f(n,k,m)打了一个小表,什么都尚未意识。
20分钟左右本身初叶稳定k和m,移动n。
试验了几组k在2~4的数量后意识从n到n+1,答案会增高m^(k-1)。
试到30分钟,总计出:规律是在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)。
试到30分钟,计算出:规律是在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

先是立时过去没什么规律?
乱搞到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。
下一场再整理一下就会收获答案:

对!因为难点有限支撑了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)

50分钟不到开打,一个钟头不到就做完了。
置身省选里面那几个日子是可以承受的(NOIPT2也是1h左右啊?)。

其一时候大家不可能满足是吧?要领悟正解是什么样。
率先步:将原数组差分,得到k-1个[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)。
接下来前边那些东西,网上的知晓我推不出去,是要对此每个东西单独考虑?不会。

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

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

以此时候大家不可以满足是吧?要通晓正解是什么。
率先步:将原数组差分,获得k-1个[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)。
然后前边那一个东西,网上的精晓自己推不出去,是要对此每个东西单独考虑?不会。

相关文章