SHARE
TWEET

Untitled

a guest Oct 19th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. template <typename T>
  8. void print(T *a, int n) {
  9.     for (int i = 1; i < n; ++i)
  10.         cout << a[i] << " " ;
  11.     cout << a[n] << endl;
  12. }
  13.  
  14. int n, m;
  15. ll t;
  16. char op;
  17.  
  18. const int N = 15;
  19. bool poss[N][N];
  20. bool vis[N][N];
  21. int rmsk[N];
  22. int cmsk[N];
  23. ll p9[N];
  24. int lookup[1 << 10];
  25. pair<int, int> pts[N];
  26.  
  27. inline int lowbit(int x) {
  28.     return x & (-x);
  29. }
  30.  
  31. template<typename T>
  32. int go(int idx, int nvis, T cur) {
  33.     if (op == '+' && cur + 9 * (m - nvis) < t)
  34.         return 0;
  35.     if (op == '+' && cur + (m - nvis) > t)
  36.         return 0;
  37.     if (op == '*' && (cur * p9[m - nvis] < t || cur > t))
  38.         return 0;
  39.     int r = pts[idx].first;
  40.     int c = pts[idx].second;
  41.     if (nvis + 1 == m) {
  42.         if (op == '+') {
  43.             T last = t - cur;
  44.             if (last > n || last <= 0) return 0;
  45.             --last;
  46.             if (rmsk[r] & (1 << last)) return 0;
  47.             if (cmsk[c] & (1 << last)) return 0;
  48.             return 1;
  49.         }
  50.         if (op == '*') {
  51.             if (t % cur != 0)
  52.                 return 0;
  53.             T last = t / cur;
  54.             if (last > n) return 0;
  55.             --last;
  56.             if (rmsk[r] & (1 << last)) return 0;
  57.             if (cmsk[c] & (1 << last)) return 0;
  58.             return 1;
  59.         }
  60.     }
  61.     int ans = 0;
  62.     int msk = ((1 << n) - 1) ^ (cmsk[c] | rmsk[r]);
  63.     for ( ; msk; msk -= lowbit(msk)) {
  64.         int cur_v = lowbit(msk);
  65.         int want = lookup[cur_v] + 1;
  66.         vis[r][c] = true;
  67.         rmsk[r] ^= cur_v;
  68.         cmsk[c] ^= cur_v;
  69.         T nxt = op == '+' ? cur + want : cur * want;
  70.         ans += go(idx + 1, nvis + 1, nxt);
  71.         vis[r][c] = false;
  72.         rmsk[r] ^= cur_v;
  73.         cmsk[c] ^= cur_v;
  74.     }
  75.     return ans;
  76. }
  77.  
  78. int main() {
  79.     ios_base::sync_with_stdio(false);
  80. #ifdef CMU1
  81.     freopen("input.txt", "r", stdin);
  82.     freopen("output.txt", "w", stdout);
  83. #endif
  84.     double start_time = clock();
  85.     cin >> n >> m >> t >> op;
  86.     for (int i = 0; i < m; i++) {
  87.         int r, c;
  88.         cin >> r >> c;
  89.         pts[i] = make_pair(r, c);
  90.     }
  91.     p9[0] = 1;
  92.     for (int i = 1; i <= m; i++)
  93.         p9[i] = 9LL * p9[i - 1];
  94.     lookup[1] = 0;
  95.     int now = 1;
  96.     for (int i = 2; i <= 10; ++i) {
  97.         now *= 2;
  98.         lookup[now] = i - 1;
  99.     }
  100.     if (op == '-' || op == '/') {
  101.         if (t > 10000) {
  102.             cout << "0\n";
  103.             exit(0);
  104.         }
  105.         int tot = 0;
  106.         for (int i = 1; i <= n; i++) {
  107.             for (int j = 1; j <= n; j++) {
  108.                 if (op == '-' && max(i, j) - min(i, j) == t)
  109.                     tot++;
  110.                 if (op == '/' && i != j && min(i, j) * t == max(i, j)) {
  111.                     tot++;
  112.                 }
  113.             }
  114.         }
  115.         cout << tot << '\n';
  116.         return 0;
  117.     }
  118.     int start = (op == '+') ? 0 : 1;
  119.     ll ans = op == '+' ? go<int>(0, 0, start)
  120.                        : go<ll>(0, 0, start);
  121.     cout << ans << '\n';
  122.     return 0;
  123. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top