Türkçe

\(\mathbf{N}\) basamaklı ve rakamları toplamı \(\mathbf{K}\) olan sayıların adedini recursive olarak tanımlayabiliriz:

• Rakamları toplamı 0'dan başka bir sayı olan 0 basamaklı sayı yoktur.
• Rakamları toplamı 0 olan 0 basamaklı sayı adedi 1'dir.

Bu iki maddede basamak sayısı ve rakamları toplamı 0 olan bir sayının var olduğunu kabul etmek tanımlamamızı kolaylaştırmaya yarıyor. Aslında "Rakamları toplamı 1 olan 1 basamaklı sayı adedi 1'dir. Rakamları toplamı 2 olan 1 basamaklı sayı adedi 1'dir\(\ldots\) Bu özelliklerin herhangi birine uymayan 1 basamaklı sayı yoktur." şeklinde de tanımlayabilirdik.

• \(\mathbf{i}\) bir rakam olsun. \(\mathbf{i}\) ile başlayan, en çok \(\mathbf{N}\) basamaklı ve rakamları toplamı \(\mathbf{K}\) olan sayı adedi, en çok \(\mathbf{N-1}\) basamaklı ve rakamları toplamı \(\mathbf{K-i}\) olan sayı adedine eşittir. Öyleyse en çok \(\mathbf{N}\) basamaklı ve rakamları toplamı \(\mathbf{K}\) olan sayı adedi bütün \(\mathbf{i}\) değerleri için \(\mathbf{i}\) ile başlayan en çok \(\mathbf{N}\) basamaklı ve rakamları toplamı \(\mathbf{K}\) olan sayı adetlerinin toplamına eşittir.

Öyleyse \(\mathbf{N}\) ve \(\mathbf{K}\) ikilisi için üzerindeki görüntüsü "en çok \(\mathbf{N}\) basamaklı ve rakamları toplamı \(\mathbf{K}\) olan sayı adedi" olan fonksiyon \(C\)'yi şu şekilde tanımlayabiliriz:

\(C(\mathbf{N},\mathbf{K})=\begin{cases}0, & \mathbf{N} = 0 \land \mathbf{K} \neq 0\\ 1, & \mathbf{N} = 0 \land \mathbf{K} = 0\\ \sum_{i=0}^{9}{C(\mathbf{N}-1, \mathbf{K}-\mathbf{i})}, & otherwise\end{cases}\)

Son olarak, büyük \(\mathbf{K}\) ve \(\mathbf{N}\) ikilileri için pek çok sıralı ikilinin \(C\)'deki görüntüsü birden fazla kez berileceği için memoization tekniğinden faydalanmalıyız.

English

We can recursively define the count of \(\mathbf{N}\) digit numbers whose sum of digits are \(\mathbf{K}\) as the following:

• There are no 0-digit numbers whose sum of digits is not 0.
• There is exactly one 0-digit number whose sum of digits is 0.

Assuming that there exists a number whose number of digits is 0 eases our base case definition. We could instead define our base cases as "There exists exactly one 1-digit number whose sum of digits is 1. There exists exactly one 1-digit number whose sum of digits is 2. There exists exactly one 1-digit number whose sum of digits is 3 \(\ldots\)", which would be more complicated.

• Let \(\mathbf{i}\) be a single-digit number. The count of at most \(\mathbf{N}\)-digit numbers starting with \(\mathbf{i}\) whose sum of digits is \(\mathbf{K}\) is equal to the count of at most \(\mathbf{N-1}\)-digit numbers whose sum of digits is \(\mathbf{K-i}\). The count of at most \(\mathbf{N}\)-digit numbers whose sum of digits is \(\mathbf{K}\) is equal to the sum of the count of at most \(\mathbf{N}\)-digit numbers starting with \(\mathbf{i}\), whose sum of digits is \(\mathbf{K-i}\) for all values of \(\mathbf{i}\).

Therefore, the function \(C\), under which the pair \(\mathbf{N}\) and \(\mathbf{K}\)'s image is the count of at most \(\mathbf{N}\)-digit numbers whose sum digits is equal to \(\mathbf{K}\) can be defined as:

\(C(\mathbf{N},\mathbf{K})=\begin{cases}0, & \mathbf{N} = 0 \land \mathbf{K} \neq 0\\ 1, & \mathbf{N} = 0 \land \mathbf{K} = 0\\ \sum_{i=0}^{9}{C(\mathbf{N}-1, \mathbf{K}-\mathbf{i})}, & otherwise\end{cases}\)

Finally, since for great \(\mathbf{K}\) and \(\mathbf{N}\) values, images of various pairs under \(C\) is computed several times, we need to use memoization.

Örnek Çözüm / Sample Solution

#include <bits/stdc++.h>
using namespace std;

typedef long long Int;
typedef pair<int,int> PII;
typedef vector<int> VInt;

#define FOR(i, a, b) for(i = (a); i < (b); ++i)
#define RFOR(i, a, b) for(i = (a) - 1; i >= (b); --i)
#define EACH(it, a) for(auto it = (a).begin(); it != (a).end(); ++it)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define SIZE(a) int((a).size())
#define ALL(a) (a).begin(),(a).end()
#define MP make_pair

#define MOD ((int)(1e9+7))

Int Cache[1 << 10][1 << 10];
Int f(int n, int k)
{
    if(k < 0) return 0;
    if(n == 0) return k == 0 ? 1 : 0;
    Int& res = Cache[n][k];
    if(res != -1) return res;
    res = 0;
    int i;
    FOR(i, 0, 10) res += f(n - 1, k - i);
    res %= MOD;
    return res;
}

int main()
{
    int n, k;
    cin >> n >> k;    
    CLEAR(Cache, -1);
    cout << f(n, k) << endl;
    return 0;
}