[CF621E]Wet Shark and Blocks

关于

题目链接
这道题目是一道矩阵题。
题目大意是给你 b 个数表,这个数表有 n 个数字组成。从每个数表中取出一个数,组成一个数,问这个数最终能模 x 等于 k 的个选取方法有多少种。

 

分析

首先想到的是动态规划。用 a_t[n] 表示用了 t 个数之后余 n 的方法数,显然可以由且只由 a_{t-1}[n] 计算出来,而且每次计算的方式都一样。也就是说, a_t 是由 a_{t-1} 以一种固定的变换方式变换得来。所以我们就想到了生产一个 e 矩阵,用矩阵去记录它每次变换的方式,这样乘一次矩阵就相当于变换一次,那么我们只需要把矩阵乘以 n-1 次就能得到结果。
由于我们知道矩阵是满足结合律的,所以可以用二分快速幂(传送门)。
这样,时间复杂度就可以优化到 O(x^3\ log(n))
注意开long long。

 

代码

代码比较丑

 

未完结

One thought on “[CF621E]Wet Shark and Blocks

  1. Pingback: Codeforces Round #341 (Div. 2) | 火药

发表评论

电子邮件地址不会被公开。 必填项已用*标注