1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
const LL Mod=1000000007;
int k0;
LL cnt[20][20*9], sum[20][20*9];
void dp(int n)
{
    int sign=-1;
    cnt[0][k0]=1; sum[0][k0]=0;
    for (int i=0; i<n; ++i)
    {
        sign=-sign;
        for (int j=-i/2*9; j<=(i+1)/2*9; ++j)
            for (int l=0; l<=9; ++l)
            {
                int x=j+sign*l+k0;
                cnt[i+1][x]=(cnt[i+1][x]+cnt[i][j+k0])%Mod;
                sum[i+1][x]=(sum[i+1][x]+sum[i][j+k0]*10+cnt[i][j+k0]*l)%Mod;
            }
    }
}
LL calc(int n, int k)
{
    if (n<=0) return 0;
    LL res=calc(n-1, k);
    LL base=1;
    for (int i=1; i<n; ++i) base*=10;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX