数位 DP 的前缀约束

#include <bits/stdc++.h>
using namespace std;

int main() {
string bound="25";long long dp[2][2]={};dp[1][0]=1;
for(char c:bound){long long next[2][2]={};for(int tight=0;tight<2;++tight)for(int seen=0;seen<2;++seen)for(int d=0;d<=(tight?c-'0':9);++d)next[tight&&d==c-'0'][seen||d==2]+=dp[tight][seen];for(int t=0;t<2;++t)for(int s=0;s<2;++s)dp[t][s]=next[t][s];}
cout<<dp[0][1]+dp[1][1]<<" "<<dp[0][0]+dp[1][0];
}

#include <bits/stdc++.h>
using namespace std;

int main() {
string bound="25";long long dp[2][2]={};dp[1][0]=1;
for(char c:bound){long long next[2][2]={};for(int tight=0;tight<2;++tight)for(int seen=0;seen<2;++seen)for(int d=0;d<=(tight?c-'0':9);++d)next[tight&&d==c-'0'][seen||d==2]+=dp[tight][seen];for(int t=0;t<2;++t)for(int s=0;s<2;++s)dp[t][s]=next[t][s];}
cout<<dp[0][1]+dp[1][1]<<" "<<dp[0][0]+dp[1][0];
}