题意：1-n中有多少个数满足本身能被各个数位的和整除；
思路：n是10的12次方，很快就能想到是数位dp，当时没板子，忘了数位dp怎么敲了，后来看了下题解，还是挺裸的数位dp。
dp[pos][sum][remain][mod];
pos:代表当前数位
sum:各数位之和
remain:当前枚举的数
mod:枚举的膜
9*12=108，所以只要枚举1-108即可；
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; int a[15]; int dp[15][110][110][110]; ll dfs(int pos,int sum,int mod,int remain,bool limit) { if(!pos) return sum==mod&&remain==0; if(dp[pos][sum][remain][mod]!=-1&&!limit) return dp[pos][sum][remain][mod]; int up = limit ? a[pos] : 9; ll ans = 0; for(int i = 0; i <= up; i++) { ans += dfs(pos-1,sum+i,mod,(remain*10+i)%mod,limit&&i==up); } if(!limit) dp[pos][sum][remain][mod] = ans; return ans; } void solve(ll t) { int len = 0; while(t) { a[++len] = t; t /= 10; } ll ans = 0; for(int i = 1; i <= 108; i++) { ans += dfs(len,0,i,0,true); } cout<<ans<<endl; } int main() { //freopen("just.in","r",stdin); //freopen("just.out","w",stdout); ll m; memset(dp,-1,sizeof(dp)); cin >> m; solve(m); return 0; }