题意

题目本身没有任何背景描述和抽象化，直接题目本身就是题意

所有的长度为n的数中，各个位上的数字之和为m的这些数的和是多少呢。给定n和m，求这些数的和

$nn$n 最大是 6

方法

实现

在算法比赛内比较早的一个估计计算时间的概念是$10^{8}10^8$108次加法为$11$1秒。（虽然随着硬件升级以及编译器的一些优化可能现在已经快了不少

那么这道题 所有可能的值最大$10^{6}10^6$106, 对于一个给定的六位以内的数，计算其各个位的和，需要大约6*加法/取模/除法常数的运算量, 还是常数倍。

代码

class Solution {
public:
    int sumdigit(int v){
        int r = 0;
        while(v){
            r+=v%10;
            v/=10;
        }
        return r;
    }
    /**
     * 返回这样的数之和
     * @param n int整型 数的长度
     * @param m int整型 各个为之和
     * @return long长整型
     */
    long long sum(int n, int m) {
        long long ans = 0;
        // write code here
        int range[] = {0,10,100,1000,10000,100000,1000000};
        for(int i = range[n-1];i<range[n];i++){
            if(sumdigit(i) == m)ans+=i;
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 对于一个给定的六位以内的数，计算其各个位的和，需要常数倍数的运算量，其中$nn$n是位数, 所以总的时间复杂度为$O(n\cdot 10^n)O(n\backslash cdot\; 10^n\; )$O(n⋅10n)

空间复杂度: 空间只需要记录当前 的总和,常数大小的空间，所以空间复杂度为 $O\left(1\right)O(1)$O(1)

贡献统计/dfs+记忆化

解这道题完全用不到这个方法，但是如果n的值更大，无法通过枚举所有值来实现的时候，可以考虑用贡献统计和dfs来完成

注意到一个$nn$n位数，只有首位不能为零。考虑首位以外的进行深度搜索

f(总和,位数) = 方案数

那么有关系式

$f(cnt,sz)={\sum }_{i=\mathrm{0..9}}f(cnt-i,sz-1)f(cnt,sz)\; =\; \backslash sum\_\{i\; =\; 0..9\}\{f(cnt-i,sz-1)\}$f(cnt,sz)=∑i=0..9​f(cnt−i,sz−1)

我们可以通过cnt<0,cnt>9∗sz,sz==1,sz==0 进行一定的边界判断，通过记忆化$mapmap$map 能保证所有状态最多搜一次

这样我能计算出除了首位的剩余的方案数，令它为$ww$w，

这道题要求的是所有数字的和,

首位在总和的贡献为$w\cdot 首位\cdot 10^{n-1}w\; \backslash cdot\; 首位\; \backslash cdot\; 10^\{n-1\}$w⋅首位⋅10n−1

剩余位置所有值的和是$w\cdot (m-首位)w\; \backslash cdot\; (m-首位)$w⋅(m−首位), 剩余位置是等概率期望的，所以每一位的和值是$\frac{w\cdot (m-首位)}{n-1}\backslash frac\{w\; \backslash cdot\; (m-首位)\; \}\{n-1\}$n−1w⋅(m−首位)​, 然后把它们乘上$\mathrm{11..1}11..1$11..1, 就是总和,其中$\mathrm{11..1}=\frac{\mathrm{99..9}}{9}=\frac{10^{n-1}-1}{9}11..1\; =\; \backslash frac\{99..9\}\{9\}\; =\; \backslash frac\{10^\{n-1\}-1\}\{9\}$11..1=999..9​=910n−1−1​

那么 答案为

$ans={\sum }_{i=\mathrm{1..9}}(10^{n-1}\cdot i\cdot f(m-i,n-1)+\frac{w\cdot (m-i)}{n-1}\cdot \frac{10^{n-1}-1}{9})ans\; =\; \backslash sum\_\{i=1..9\}\; (10^\{n-1\}\; \backslash cdot\; i\; \backslash cdot\; f(m-i,n-1)\; +\; \backslash frac\{w\backslash cdot(m-i)\}\{n-1\}\; \backslash cdot\; \backslash frac\{10^\{n-1\}-1\}\{9\})$ans=∑i=1..9​(10n−1⋅i⋅f(m−i,n−1)+n−1w⋅(m−i)​⋅910n−1−1​)

以题目的样例数据$2,32,3$2,3为例

首位1, $(m-i,n-1)=(3-1,2-1)=(2,1)(m-i,n-1)\; =\; (3-1,2-1)\; =\; (2,1)$(m−i,n−1)=(3−1,2−1)=(2,1)

dfs(cnt,sz) 为

也就是说明，长度为$n=2n=2$n=2,总和$m=3m=3$m=3，的情况下，$11$1放在首位有$11$1种方案

那么首位的对总和的贡献是$1\cdot 1\cdot 101\backslash cdot\; 1\; \backslash cdot\; 10$1⋅1⋅10, 而首位以外的贡献是$\frac{1\cdot (3-1)}{1}\cdot 1\backslash frac\{1\backslash cdot\; (3-1)\}\{1\}\; \backslash cdot\; 1$11⋅(3−1)​⋅1

以数据$3,43,4$3,4为例

首位1, $(m-i,n-1)=(4-1,3-1)=(3,2)(m-i,n-1)\; =\; (4-1,3-1)\; =\; (3,2)$(m−i,n−1)=(4−1,3−1)=(3,2)

dfs(cnt,sz) 为

也就是说明，长度为$n=3n=3$n=3,总和$m=4m=4$m=4，的情况下，$11$1放在首位有$44$4种方案

那么首位的对总和的贡献是$1\cdot 4\cdot 1001\backslash cdot\; 4\; \backslash cdot\; 100$1⋅4⋅100, 而首位以外的贡献是$\frac{4\cdot (4-1)}{2}\cdot 11\backslash frac\{4\backslash cdot\; (4-1)\}\{2\}\; \backslash cdot\; 11$24⋅(4−1)​⋅11

代码

class Solution {
public:
    map<pair<int,int>,long long> cntsz2val; // 记忆化
    long long ways(long long cnt,long long sz){
        if(sz * 9 < cnt)return 0;
        if(cnt < 0) return 0;
        if(sz == 1) return 1;
        if(sz == 0) return cnt == 0;
        if(cntsz2val.count(make_pair(cnt,sz))){
            return cntsz2val[make_pair(cnt,sz)];
        }
        // 当前位置放i
        for(int i = 0;i < 10;i++){
            cntsz2val[make_pair(cnt,sz)] += ways(cnt-i,sz-1); // 状态转移
        }
        return cntsz2val[make_pair(cnt,sz)];
    }
    /**
     * 返回这样的数之和
     * @param n int整型 数的长度
     * @param m int整型 各个为之和
     * @return long长整型
     */
    long long sum(int n, int m) {
        long long ans = 0;
        // write code here
        int range[] = {0,10,100,1000,10000,100000,1000000};
        if(n == 1)return m;
        // 首位
        for(int i = 1;i<10;i++){
            long long w = ways(m-i,n-1);
            ans += i * range[n-1] * w + (m-i) * w / (n-1) * ((range[n-1]-1)/9);
        }
        return ans;
    }
};

这道题如果n对应变大，那么就可以使用这种方法，因为$m\le 9nm\backslash leq\; 9n$m≤9n, 所以我们$n=100n=100$n=100 也是能在1s内完成的

复杂度分析

空间复杂度: 我们为了减少dfs中的重复计算，有状态[剩余个数][剩余位数],所以空间复杂度$O\left(mn\right)O(mn)$O(mn)

时间复杂度: 对于所有状态我们进行了dfs了，状态转移过程是每次第一个位置放0~10,是常数级别的状态转移,所以总的时间为 转移代价x状态数，也是$O\left(mn\right)O(mn)$O(mn)

知识点

1. int加法注意溢出问题，用long long 来保存和
2. 大概的1秒能计算多少次，在写代码之前就能估计所使用的算法复杂度是否能满足题目时限，打算法时，有时数据范围小的情况暴力实现即可