luogu3107

洛谷P3107题面

相对较为模板化的代码 f[i][j][bo1][bo2]记录到第i位，数字num出现了x次（j初始为20，若当前数字不为num，j++；否则j--；最后只要记录j<=20的总和）bo1和bo2就很简单了，上界和前导零

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
#define int long long
string l,r;
int f[25][55][2][2],kkk[20];
inline int DP(int le,int num1,int num2)
{
    int re=0,i,bo1,bo2,j,k,bo,pp; memset(f,0,sizeof f); f[0][20][1][1]=1;
    //bo1:上界 bo2:前导零 
    for(i=0;i<le;i++)
    {
        for(j=0;j<=50;j++)
        {
            for(bo1=0;bo1<2;bo1++)
            {
                for(bo2=0;bo2<2;bo2++)
                {
                    if(f[i][j][bo1][bo2]==0)continue;
                    for(k=0;k<=9;k++)
                    {
                        if((num2!=-1&&(k!=0||!bo2)&&k!=num1&&k!=num2)||(bo1&&k>kkk[i]))continue; pp=j;
                        if(!bo2||k!=0)
                        {
                            if(num2==-1)
                            {
                                if(k==num1)pp--;else pp++;
                            }
                            else
                            {
                                if(k==num1)pp--;else if(k==num2)pp++;
                            }
                        }f[i+1][pp][bo1&(k==kkk[i])][bo2&(k==0)]+=f[i][j][bo1][bo2];
                    }
                }
            }
        }
    }
    if(num2==-1)
    {
        for(i=0;i<=20;i++)for(j=0;j<2;j++)re+=f[le][i][j][0];
    }else for(i=0;i<2;i++)re+=f[le][20][i][0];
    return re;
}
inline int solve(string s)
{
    int re=0,i,j,le=s.size();
    for(i=0;i<le;i++) kkk[i]=s[i]-'0';
    for(i=0;i<=9;i++) re+=DP(le,i,-1);
    for(i=0;i<9;i++)
    {
        for(j=i+1;j<=9;j++)re-=DP(le,i,j);
    }return re;
}
signed main()
{
    int i; cin>>l>>r;
    for(i=l.size()-1;i>=0;i--)
    {
        if(l[i]=='0')l[i]='9';else {l[i]--;break;}
    }printf("%lld
",solve(r)-solve(l));
}