题意：
给你三个数字L, R, K，问在[L, R]范围内有多少个数字满足它每一位不同数字不超过k个，求出它们的和
思路：
明显的数位DP了，套路都一样，不过这道题是记权值而不是满足条件的数字个数，所以还需要再开一个计贡献数组
dp[len][x][sum]表示当前有len位数字还不确定，在此之前0~9每个数字出现的状态为x，已经有sum个不同数字的方案个数
#include<stdio.h>#include<string.h>#include<algorithm>#include<map>#include<assert.h>#include<string>#include<math.h>#include<queue>#include<stack>#include<iostream>using namespace std;#define LL long long#define mod 998244353int k, str[24];typedef struct Res{LL cnt;LL sum;}Res;Res temp, dp[24][1025][25];LL ten[25] = {1};Res Sech(int len, int now, int sum, int flag, int p){int u, i;LL ans, cnt;if(sum>k){t = temp.sum = 0;return temp;}if(len==0){temp.sum = 0, t = 1;return temp;}if(flag==0 && p==0 && dp[len][now][sum].cnt!=-1)return dp[len][now][sum];if(flag==1) u = str[len];else u = 9;ans = cnt = 0;for(i=0;i<=u;i++){if(now&(1<<i)){temp = Sech(len-1, now, sum, flag&&i==u, 0);cnt += t;ans = (ans+temp.sum+t%mod*i%mod*ten[len-1])%mod;}else{if(p==1 && i==0){temp = Sech(len-1, now, sum, flag&&i==u, 1);cnt += t;ans = (ans+temp.sum)%mod;}else{temp = Sech(len-1, now^(1<<i), sum+1, flag&&i==u, 0);cnt += t;ans = (ans+temp.sum+t%mod*i%mod*ten[len-1])%mod;}}}t = cnt;temp.sum = ans;if(flag==0 && p==0)dp[len][now][sum] = temp;return temp;}Res Jud(LL x){int len = 0;len = 0;while(x){str[++len] = x%10;x /= 10;}return Sech(len, 0, 0, 1, 1);}int main(void){LL l, r, i;for(i=1;i<=22;i++)ten[i] = ten[i-1]*10%mod;memset(dp, -1, sizeof(dp));scanf("%lld%lld%d", &l, &r, &k);printf("%lld\n", (Jud(r).sum-Jud(l-1).sum+mod)%mod);return 0;}/*1250 236927938 0*/
