fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template<typename F, typename S>
  5. ostream &operator<<(ostream &os, const pair<F, S> &p) {
  6.     return os << "(" << p.first << ", " << p.second << ")";
  7. }
  8.  
  9. template<typename T>
  10. ostream &operator<<(ostream &os, const vector<T> &v) {
  11.     os << "{";
  12.     typename vector<T>::const_iterator it;
  13.     for (it = v.begin(); it != v.end(); it++) {
  14.         if (it != v.begin()) os << ", ";
  15.         os << *it;
  16.     }
  17.     return os << "}";
  18. }
  19.  
  20. template<typename T>
  21. ostream &operator<<(ostream &os, const set<T> &v) {
  22.     os << "[";
  23.     typename set<T>::const_iterator it;
  24.     for (it = v.begin(); it != v.end(); it++) {
  25.         if (it != v.begin()) os << ", ";
  26.         os << *it;
  27.     }
  28.     return os << "]";
  29. }
  30.  
  31. template<typename F, typename S>
  32. ostream &operator<<(ostream &os, const map<F, S> &v) {
  33.     os << "[";
  34.     typename map<F, S>::const_iterator it;
  35.     for (it = v.begin(); it != v.end(); it++) {
  36.         if (it != v.begin()) os << ", ";
  37.         os << it->first << " = " << it->second;
  38.     }
  39.     return os << "]";
  40. }
  41.  
  42. #define debug(x) cerr << #x << " = " << x << endl;
  43. #define trace1(x)                cerr<<#x<<": "<<x<<endl
  44. #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  45. #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  46. #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  47. #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  48. #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  49.  
  50.  
  51. typedef long long int ll;
  52. typedef long double ld;
  53. typedef vector<int> vi;
  54. typedef vector<long long int> vll;
  55. typedef pair<int, int> pii;
  56. typedef pair<long long int, long long int> pll;
  57. typedef map<int, int> mii;
  58. typedef vector< pair<int, int> > vpii;
  59.  
  60. #define endl "\n";
  61. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  62. #define pb push_back
  63. #define mp make_pair
  64. #define all(c) (c).begin(),(c).end()
  65. #define tr(cont, it) for(decltype((cont).begin()) it = (cont).begin(); it != (cont).end(); it++)
  66. #define present(c, x) ((c).find(x) != (c).end())
  67. #define cpresent(c, x) (find(all(c),x) != (c).end())
  68. #define F first
  69. #define S second
  70.  
  71.  
  72. const ld PI=acos(-1.0);
  73. const ll mod = 1000000007;
  74. const ll inf = (ll) 1e15;
  75.  
  76. ll power(ll a, ll b, ll m = mod) {if (b == 0) return 1; if (b == 1) return (a % m); ll x = power(a, b / 2, m); x = (x * x) % m; if (b % 2) x = (x * a) % m;return x;}
  77. ll max(ll a, ll b) { return (a > b ? a : b); }
  78. ll min(ll a, ll b) { return (a < b ? a : b); }
  79.  
  80. const int N=11;
  81. const int M=1e5+5;
  82.  
  83. int n,k;
  84. bool a[N];
  85. ll l,r;
  86. string s;
  87. ll dp[20][3][11][11][2555][3];
  88. set<string> s1,s2;
  89. int x;
  90.  
  91. ll func(int idx,bool isless,int rem,int prev,int occur,bool inc)
  92. {
  93.     if(rem<=0)
  94.         return 0;
  95.     if(idx==s.size())
  96.     {
  97.         // debug(idx);
  98.         for(int i=1;i<=9;i++)
  99.         {
  100.             if(a[i])
  101.             {
  102.                 if(occur&(1<<i))
  103.                     continue;
  104.                 else
  105.                     return 0;
  106.             }
  107.         }
  108.         return 1;
  109.     }
  110.     if(dp[idx][isless][rem][prev][occur][inc]!=-1)
  111.         return dp[idx][isless][rem][prev][occur][inc];
  112.     ll ret=0;
  113.     if(inc)
  114.     {
  115.         for(int i=prev+1;i<=9;i++)
  116.         {
  117.             if(isless== false && i>(s[idx]-'0'))
  118.                 continue;
  119.             if(isless== false && i==(s[idx]-'0'))
  120.             {
  121.                 ret+=func(idx+1, false,rem-1,i,occur|(1<<i),true);
  122.                 continue;
  123.             }
  124.             ret+=func(idx+1,true,rem-1,i,occur|(1<<i),true);
  125.         }
  126.         for(int i=prev-1;i>=0;i--)
  127.         {
  128.             if(i==0 && prev!=0)
  129.                 continue;
  130.             if(isless== false && i>(s[idx]-'0'))
  131.                 continue;
  132.             if(isless== false && i==(s[idx]-'0'))
  133.             {
  134.                 ret+=func(idx+1,false,k-1,i,occur|(1<<i), false);
  135.                 continue;
  136.             }
  137.             ret+=func(idx+1,true,k-1,i,occur|(1<<i),false);
  138.         }
  139.     }
  140.     else
  141.     {
  142.         //decresing
  143.         for(int i=prev-1;i>=0;i--)
  144.         {
  145.             if(i==0 && prev!=0)
  146.                 continue;
  147.             if(isless== false && i>(s[idx]-'0'))
  148.                 continue;
  149.             if(isless== false && i==(s[idx]-'0'))
  150.             {
  151.                 ret+=func(idx+1,false,rem-1,i,occur|(1<<i), false);
  152.                 continue;
  153.             }
  154.             ret+=func(idx+1,true,rem-1,i,occur|(1<<i),false);
  155.         }
  156.         for(int i=prev+1;i<=9;i++)
  157.         {
  158.             if(isless== false && i>(s[idx]-'0'))
  159.                 continue;
  160.             if(isless== false && i==(s[idx]-'0'))
  161.             {
  162.                 ret+=func(idx+1, false,k-1,i,occur|(1<<i),true);
  163.                 continue;
  164.             }
  165.             ret+=func(idx+1,true,k-1,i,occur|(1<<i),true);
  166.         }
  167.     }
  168.       //trace2(ret,idx);
  169.     return dp[idx][isless][rem][prev][occur][inc]=ret;
  170. }
  171.  
  172. void solve() 
  173. {
  174.     for (int i = 1 ; i <= 9 ; i++)
  175.         a[i] = false;
  176.     cin >> n ;
  177.     for(int i=1;i<=n;i++)
  178.     {
  179.         int idx;
  180.         cin >> idx;
  181.         a[idx]=true;
  182.     }
  183.     cin >> k;
  184.     cin >> l >> r;
  185.     l--;
  186.     s.resize(0);
  187.     s=to_string(r);
  188.     x=1;
  189.     memset(dp,-1, sizeof(dp));
  190.     // debug(s);
  191.     ll ans1=func(0,0,k,0, 0, true)+func(0,0,k,10, 0, false);
  192.     for(int i=1;i<s.size();i++)
  193.     {
  194.         ans1+=(func(i,true,k,0,0,true)+func(i,true,k,10,0,false));
  195.     }
  196.     x=2;
  197.     s.resize(0);
  198.     s=to_string(l);
  199.     memset(dp,-1, sizeof(dp));
  200.     ll ans2=func(0,0,k,0, 0, true)+func(0,0,k,10, 0, false);
  201.     for(int i=1;i<s.size();i++)
  202.     {
  203.         ans2+=(func(i,true,k,0,0,true)+func(i,true,k,10,0,false));
  204.     }
  205.     trace2(ans1,ans2);
  206.     cout << ans1- ans2 << endl;
  207. }
  208.  
  209. int main() {
  210.     IOS;
  211.     int t = 1, num = 1;   ///// change this t for number of testcase globally
  212.     cin >> t;
  213.     while (t--) {
  214.         solve();
  215.     }
  216.     return 0;
  217. }
  218.  
  219. /* stuff you should look for
  220.     * int overflow, array bounds
  221.     * special cases (n=1?), set tle
  222.     * do smth instead of nothing and stay organized
  223. */
  224.  
Success #stdin #stdout #stderr 0.17s 449984KB
comments (?)
stdin
copy 
2
2
1 2
2
10 200
3
3 5 7
3
100000 200000
stdout
copy 
10
3140
stderr
copy 
ans1: 10 | ans2: 0
ans1: 7476 | ans2: 4336
https://ideone.com/dzWvvU
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!