题解|月之谜

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 10;

int f[N*N][N][N*N][N*N],power[10];
int n=9,m=81, num[10];

int ask(int x)
{
    int res = 0, d = 0;
    for(int t=x; t; t/=10) d++;
    for(int i=1; i<=d; i++) num[i] = x % 10, x /= 10;
    for(int sum=1; sum<=d*9; sum++) { // 枚举数位之和
        int nowsum = 0, nowx = 0;
        for(int i=d; i>=1; i--) { // 选到第几位
            for(int j=0; (i == 1 ? j <= num[i] : j < num[i]) && sum - nowsum - j >= 0; j++)
                res += f[sum][i-1][sum-nowsum-j][(sum-(nowx+j*power[i-1])%sum+sum)%sum];
            nowsum += num[i], nowx = (nowx + num[i] * power[i-1]) % sum;
        }
    }
    return res;
}

int main()
{
    power[0] = 1;
    for(int i=1;i<=n;i++)power[i] = power[i-1] * 10;

    for(int mod=1;mod<=m;mod++)
    {
        f[mod][0][0][0] = 1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                for(int k=0;k<mod;k++)
                {
                    for(int p=0;p<=n &&p <= j;p++)
                    {
                        f[mod][i][j][k]+=f[mod][i-1][j-p][(k-p*power[i-1]%mod+mod)%mod];
                    }
                }
            }
        }
    }

    int l,r;
    while(cin >> l >> r){  cout<<ask(r) - ask(l-1);  }
    
}