蒟蒻30分求助,写了个数位DP
查看原帖
蒟蒻30分求助,写了个数位DP
427060
甲虫独白楼主2021/9/1 14:47
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
typedef unsigned long long ll;
ll a,b;
ll dp[15][10][10];
ll res1[10];
ll res2[10];
void init()
{
    for(int i=0;i<=9;i++)   dp[1][i][i]=1;
    ll power=10;
    for(int i=2;i<=13;i++,power*=10)
       for(int j=0;j<=9;j++)
       {
         for(int h=0;h<=9;h++)
         {

           for(int k=0;k<=9;k++)
              dp[i][j][h]+=dp[i-1][k][h];
         }
                dp[i][j][j]+=power;
       }
      
}

void dpdp(ll n,ll res[])
{
for(int k=0;k<=9;k++)
    res[k]=0;
    if(n<=9)
    {
        for(int i=0;i<=n;i++)
        res[i]++;
        return;
    }
    vector<ll> ss;
    
    while(n) ss.push_back(n%10),n/=10;
    for(int i=ss.size()-1;i>=0;i--)
    {

        int z=ss[i];
        if(z==0) continue;
        for(int j = i==ss.size()-1;j<z;j++)
        {
            for(int k=0;k<=9;k++)
            res[k]+=dp[i+1][j][k];
        }

        
    }
        for(int i=ss.size()-1;i>0;i--)
        {
            for(int j=1;j<=9;j++)
            {
                for(int k=0;k<=9;k++)
                res[k]+=dp[i][j][k];
            }
        }
        
           res[0]++;
          ll sum=0,power=1;
          res[ss[0]]++;
        for(int p=0;p<=ss.size()-2;p++,power*=10)  
        {
            sum+=power*ss[p];
            res[ss[p+1]]+=(sum+1);
        }
       
}

int main()
{
    scanf("%d%d",&a,&b);
    init();
    dpdp(a-1,res1);
    dpdp(b,res2);
    for(int k=0;k<=9;k++)
    printf("%lld ",res2[k]-res1[k]);
    return 0;
}

2021/9/1 14:47
加载中...