题目链接
P3107 [USACO14OPEN] Odometer S
解题思路
数位 dp 模板。
令某个数的特殊数字为在一个数字中至少出现过一半的数位的数字。
首先我们可以依次拆分数位来枚举当某个数位为特殊数字时来进行数位 dp，状态为 \(dp_{last,len,num,sum,\_1,\_0}\) 来代表还剩余 \(last\) 个数位需要处理，当前去除先导零时的当前数字的位数为 \(len\)，当前的特殊数字为 \(num\)，当前出现的特殊数字的次数为 \(sum\)，\(\_1\) 表示当前的位数是否取满，\(\_0\) 表示当前数字是否当前取的数字不全为零。
但是这样是不对的，为什么呢？你会发现，可能会有 \(114414\) 这样类型的数字，这种数字会分别在以 \(1\) 为特殊数字时被计算一次，以 \(4\) 为特殊数字时计算一次，你会发现，这个数字对答案的贡献被重复计算了。
然后我们可以发现，一个数字会被重复计算当且仅当：
-
这个数字有两种不同的数位。
-
这个数字出现过的两种数位的出现次数相等。
这个部分也是数位 dp 板子。
状态为 \(dp_{last,len,num1,num2,sum1,sum2,\_1,\_0}\) 来代表还剩余 \(last\) 个数位需要处理，当前去除先导零时的当前数字的位数为 \(len\)，当前的特殊数字 \(1\) 为 \(num1\)，当前的特殊数字 \(2\) 为 \(num2\)，当前出现的特殊数字 \(1\) 次数为 \(sum\)，当前出现的特殊数字 \(2\) 次数为 \(sum2\)，\(\_1\) 表示当前的位数是否取满，\(\_0\) 表示当前数字是否当前取的数字不全为零。
与前面的答案简单容斥一下即可。
参考代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll i=a;i<=b;i++)
#define forr(i,a,b) for(re ll i=a;i>=b;i--)
#define forll(i,a,b,c) for(re ll i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(re ll i=a;i>=b;i-=c)
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define db long double
#define ull unsigned long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
#define maxqueue priority_queue<ll>
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>
void Max(ll&x,ll y){x=max(x,y);}
void Min(ll&x,ll y){x=min(x,y);}
ll t;
ll l,r;
ll a[20],k;
ll dp[20][20][15][20][2][2];
int dp2[20][20][10][10][10][10][2][2];
__int128 ans;
ll dfs(ll last,ll len,ll num,ll sum,ll _1,ll _0)
{
if(last==0)
return sum*2>=len && sum && len && _0;
if(dp[last][len][num][sum][_1][_0]>=0)
return dp[last][len][num][sum][_1][_0];
ll maxn=_1?a[last]:9,ans=0;
forl(i,0,maxn)
ans+=dfs(last-1,len+(_0||(i!=0)),num,sum+(i==num && (_0 || (i!=0))),_1&&(i==maxn),_0||(i!=0));
dp[last][len][num][sum][_1][_0]=ans;
return ans;
}
ll dfs2(ll last,ll len,ll num,ll num2,ll sum,ll sum2,ll _1,ll _0)
{
Min(sum,9ll),Min(sum2,9ll);
if(last==0)
return sum+sum2==len && sum && len && _0 && sum2 && sum==sum2;
if(dp2[last][len][num][num2][sum][sum2][_1][_0]>=0)
return dp2[last][len][num][num2][sum][sum2][_1][_0];
ll maxn=_1?a[last]:9,ans=0;
forl(i,0,maxn)
ans+=dfs2(last-1,len+(_0||(i!=0)),num,num2,sum+(i==num && (_0 || (i!=0))),sum2+(i==num2 && (_0 || (i!=0))),_1&&(i==maxn),_0||(i!=0));
dp2[last][len][num][num2][sum][sum2][_1][_0]=ans;
return ans;
}
ll sol(ll x,ll y)
{
k=0;
while(x)
a[++k]=x%10,x/=10;
return dfs(k,0,y,0,1,0);
}
ll sol2(ll x,ll y,ll z)
{
k=0;
while(x)
a[++k]=x%10,x/=10;
return dfs2(k,0,y,z,0,0,1,0);
}
void solve()
{
forl(i,0,19)
forl(j,0,19)
forl(ii,0,14)
forl(jj,0,19)
forl(iii,0,1)
forl(jjj,0,1)
dp[i][j][ii][jj][iii][jjj]=-1;
forl(i,0,19)
forl(j,0,19)
forl(ii,0,9)
forl(jj,0,9)
forl(iii,0,9)
forl(jjj,0,9)
forl(iiii,0,1)
forl(jjjj,0,1)
dp2[i][j][ii][jj][iii][jjj][iiii][jjjj]=-1;
cin>>l>>r;
forl(i,0,9)
ans+=sol(r,i);
forl(i,0,19)
forl(j,0,19)
forl(ii,0,14)
forl(jj,0,19)
forl(iii,0,1)
forl(jjj,0,1)
dp[i][j][ii][jj][iii][jjj]=-1;
forl(i,0,9)
ans-=sol(l-1,i);
forl(i,0,9)
forl(j,i+1,9)
ans-=sol2(r,i,j);
forl(i,0,19)
forl(j,0,19)
forl(ii,0,9)
forl(jj,0,9)
forl(iii,0,9)
forl(jjj,0,9)
forl(iiii,0,1)
forl(jjjj,0,1)
dp2[i][j][ii][jj][iii][jjj][iiii][jjjj]=-1;
forl(i,0,9)
forl(j,i+1,9)
ans+=sol2(l-1,i,j);
ll an=ans;
cout<<an<<endl;
}
int main()
{
IOS;
t=1;
// cin>>t;
while(t--)
solve();
QwQ;
}