1.??https://atcoder.jp/contests/abc135/tasks/abc135_d??

題意 ： 給一個只包含 '?' 和數(shù)字'0'~'9'的字符串,? 可以把每個'?' 轉(zhuǎn)換成 0 ~ 9 中的任意一個數(shù)字，求問整個字符串組成的數(shù)字中對13取膜后的余數(shù)為5的個數(shù)是多少. 由于答案很大，因此答案對1e9+7取模.

思路 ： dp[i][j] 用前i個字符組成的數(shù)字對13取余的結(jié)果為j的個數(shù)是多少。。對13取余只有0~12這12種情況。如果當(dāng)前字符是一個問號，那么我們從0~9對當(dāng)前位置的數(shù)字進行枚舉，然后我們發(fā)現(xiàn)，假設(shè)枚舉當(dāng)前位之前的數(shù)字是a， 當(dāng)前數(shù)字用b代替，那么有如下的式子， (10 * a + b) % 13 =? (10 * (a % 13) + b % 13), 而 a % 13 是當(dāng)前位之前的所有字符組成的數(shù)字對13取余得到的結(jié)果，因此也就可以根據(jù)i-1, 和i對13取余的式子很容易看出來怎么寫轉(zhuǎn)移方程了。邊界條件是dp[0][0] = 1。最后我們需要的答案是dp[n][5]即為所求.。