제출 #1314089

#제출 시각아이디문제언어결과실행 시간메모리
1314089boclobanchatPalindrome-Free Numbers (BOI13_numbers)C++20
95 / 100
1 ms332 KiB
#include<bits/stdc++.h> using namespace std; long long dp[22][12][12][2],dig[22]; bool kc[22][12][12][2]; long long f(int n,int a,int b,bool ck,bool st) { if(n<0) return 1; if(ck) { long long ans=0; for(int j=0;j<=dig[n];j++) { if(!st&&j==0) ans+=f(n-1,a,b,ck&(j==dig[n]),false); else if(j!=a&&j!=b) ans+=f(n-1,b,j,ck&(j==dig[n]),true); } return ans; } else { if(kc[n][a][b][st]) return dp[n][a][b][st]; kc[n][a][b][st]=true; long long ans=0; for(int j=0;j<=9;j++) { if(!st&&j==0) ans+=f(n-1,a,b,false,false); else if(j!=a&&j!=b) ans+=f(n-1,b,j,false,true); } return dp[n][a][b][st]=ans; } } long long solve(long long val) { if(val==0) return 0; int cnt=0; while(val) dig[cnt++]=val%10,val/=10; return f(cnt-1,11,10,true,false); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long l,r; cin>>l>>r; cout<<solve(r)-solve(l-1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...