hdu 3652 B-number (带整除的数位dp )

题目链接
题意:给出n,问[1,n]中,满足包含“13”且这个数(不是各位的和)能被13整除的数的个数。
思路:依然是数位dp..不过有一个小tip。。

由于包含13的情况非常难考虑(包含一个“13”,两个“13”…..)

所以要从反面考虑,即不包含13的情况。

但是由于还有另一个条件。

做法是把能被13整除的数考虑成全集U,然后在U中做分划,一部分是含13的,另一部分是不含13的。

这样我们要求两个答案,一个是能被13整除的,另一个是能被13整除并且不含13的,相减即为题目所求。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz