fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define vi vector<int>
  6. #define vvi vector<vi>
  7. #define mp make_pair
  8. #define pb push_back
  9. #define ff first
  10. #define ss second
  11. #define mod 1000000007ll
  12. #define all(c) c.begin(), c.end()
  13. #define fast_io ios_base::sync_with_stdio(0), cin.tie(0)
  14.  
  15. int fac[100005];
  16.  
  17. int power(int a, int b)
  18. {
  19.     int ans = 1;
  20.     while (b)
  21.     {
  22.         if (b & 1)
  23.             ans = (ans * a) % mod;
  24.  
  25.         a = (a * a) % mod;
  26.         b >>= 1;
  27.     }
  28.     return ans;
  29. }
  30.  
  31. int mod_inverse(int n)
  32. {
  33.     return power(n, mod - 2);
  34. }
  35.  
  36. int ncr(int n, int r)
  37. {
  38.     if (n < r)
  39.         return 0;
  40.     return (fac[n] * mod_inverse(fac[r]) % mod * mod_inverse(fac[n - r]) % mod) % mod;
  41. }
  42.  
  43. int32_t main()
  44. {
  45.     fast_io;
  46.     fac[0] = fac[1] = 1;
  47.     for (int i = 2; i < 100005; i++)
  48.         fac[i] = (i * fac[i - 1]) % mod;
  49.  
  50.     int t = 1;
  51.     cin >> t;
  52.     while (t--)
  53.     {
  54.         int ways = 1;
  55.         int n;
  56.         cin >> n;
  57.         string s;
  58.         cin >> s;
  59.  
  60.         bool consecutive = false;
  61.         int cnt = 0, left_limit = 1, right_limit = 1;
  62.  
  63.         for (int i = 0; i < n; i++)
  64.         {
  65.             if (s[i] == '-')
  66.             {
  67.                 consecutive = true, cnt++;
  68.             }
  69.             else
  70.             {
  71.                 consecutive = false;
  72.                 right_limit = s[i] - '0';
  73.  
  74.                 int choices = right_limit - left_limit + 1;
  75.                 ways = (ways * (ncr(choices + cnt - 1, cnt))) % mod;
  76.  
  77.                 left_limit = right_limit;
  78.                 cnt = 0;
  79.             }
  80.         }
  81.  
  82.         ways = (ways * (ncr(9 - left_limit + 1 + cnt - 1, cnt))) % mod;
  83.  
  84.         cout << ways << '\n';
  85.     }
  86.     return 0;
  87. }
Runtime error #stdin #stdout 0s 4976KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/U8cjmP
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!