BZOJ4870 [Shoi2017]组合数问题 矩阵快速幂优化DP

发布于 2017-07-26  2.57k 次阅读


[toggle hide="yes" title="题目" color=""]

Description

Input
第一行有四个整数 n, p, k, r,所有整数含义见问题描述。
1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^30 − 1

Output

一行一个整数代表答案。

Sample Input

2 10007 2 0

Sample Output

8

[/toggle]

本省的省选题,考虑所求式子的实际含义。分析可知,原式等价于“在n*k个物品中,选出物品数余数为r的方案数”,可以DP求出来。

设f[i][j]:前i个物品,选出物品数余数为j的方案总数,f[i][j]=f[i-1][j](第i个未选)+f[i-1][(j-1+k)%k](第i个选了)。

但是,由于n*k范围太大,直接DP会炸掉,而且k比较小,所以可以用O(k^3log(n*k))的时间复杂度用矩阵快速幂优化。设矩阵S(K*K)、T(K*1),将S[i][i]和S[i][(i-1+k)%k]置为1,T[0][0]置为0即可。

[toggle hide="no" title="代码" color=""]

 

[/toggle]


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974