Codeforces 621E Wet Shark and Block【dp + 矩阵快速幂】

• 金尘飘雪 发布于
• 1652 收藏

题意： 有b个blocks，每个blocks都有n个相同的0~9的数字，如果从第一个block选1，从第二个block选2，那么就构成12，问对于给定的n,b有多少种构成方案使最后模x的余数为k。 分析： dp+矩阵快速幂。 假如现在的数是m，模x余数是n，那么再从下一个block中选一个数a，a模x余数为b，那么新的数的余数就为(m∗10+a)%x，也就是(n∗10+b)%x，所以实...