codeforces #341 div 2 E. Wet Shark and Blocks (数位dp+矩阵加速)

http://codeforces.com/problemset/problem/621/E

题意:有b组数,每组数均有n个且相同。你必须在每组选一个数,组成一个新数sum,使得sum % x == k,问方案数 % (1e9+7)。

思路:数位dp.首先考虑b不是很大的一般情况。dp[i][j]表示处理到前i个块的时候结果为j的方案数。那么转移方程就是:dp[i][(j10+t)%x] = dp[i-1][j]cnt[t]  cnt[i]表示数字i出现的个数。

但是由于b很大(1E9),所以需要用矩阵加速。

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz