http://codeforces.com/gym/100623/attachments
题意:问1到n里面有多少个数满足:本身被其各个数位加起来的和整除。例如120 % 3 == 0,111 % 3 == 0,都算。
思路:老是写不出数位DP。。。
因为n最大为12位,所以取模的数最大可以是9*12 == 108,因此枚举这个模。
dfs记录的状态有:pos, sum, mod, remain, flag。
pos代表枚举到第几位,
sum代表数位之和,
mod代表当前枚举的模,
remain代表当前枚举的数,(做不出来主要昨天这里没考虑好,12 % 3和120 % 3是一样的结果)
flag代表前面是否达到上限。
然后最后判定的时候只要remain == 0 && mod == sum就是可行的状态。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 15
#define M 110
int dp[N][M][M][M], bit[N]; LL dfs(int pos, int sum, int mod, int remain, int flag) {
if(!pos) return sum == mod && remain == ;
if(~dp[pos][sum][remain][mod] && flag) return dp[pos][sum][remain][mod];
int d = flag ? : bit[pos];
LL ans = ;
for(int i = ; i <= d; i++)
ans += dfs(pos - , sum + i, mod, (remain * + i) % mod, flag || i != d);
if(flag) dp[pos][sum][remain][mod] = ans;
return ans;
} LL solve(LL n) {
int len = ;
while(n) { bit[++len] = n % ; n /= ; }
LL ans = ;
for(int i = ; i <= ; i++)
ans += dfs(len, , i, , );
return ans;
} int main() {
freopen("just.in", "r", stdin);
freopen("just.out", "w", stdout);
memset(dp, -, sizeof(dp));
LL n; cin >> n;
cout << solve(n) << endl;
return ;
}