Guest User

Untitled

a guest
Nov 23rd, 2015
125
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define MAX_N 2005
  3. #define MOD 1000000007
  4. using namespace std;
  5.  
  6. typedef vector <int> vi;
  7.  
  8. map <int, int> dp[MAX_N];
  9. int t, n, m, k, a, b, v[MAX_N];
  10. int kmsk, vm[MAX_N];
  11. bool uf[MAX_N], us[22];
  12. vi g[MAX_N], kf;
  13.  
  14. vi factorize(int x) {
  15.   vi dd;
  16.   while (x % 2 == 0) {
  17.     dd.push_back(2);
  18.     x /= 2;
  19.   }
  20.   for (int i = 3; i * i <= x; i += 2)
  21.     while (x % i == 0) {
  22.       dd.push_back(i);
  23.       x /= i;
  24.     }
  25.   if (x > 1)
  26.     dd.push_back(x);
  27.   return dd;
  28. }
  29.  
  30. int calc_mask(int x) {
  31.   vi xf = factorize(x);
  32.   memset(us, 0, sizeof us);
  33.   int mm = 0;
  34.   for (int i = 0; i < (int)xf.size(); i ++)
  35.     for (int j = 0; j < (int)kf.size(); j ++)
  36.       if (xf[i] == kf[j] && !us[j]) {
  37.     mm = mm | (1 << j);
  38.     us[j] = true;
  39.     break;
  40.       }
  41.   return mm;
  42. }
  43.  
  44. int solve(int cur, int tmsk) {
  45.   if (cur == n - 1)
  46.     return ((tmsk == kmsk) ? 1 : 0);
  47.   if (dp[cur].find(tmsk) == dp[cur].end()) {
  48.     int ta = 0;
  49.     for (int i = 0; i < (int)g[cur].size(); i ++)
  50.       if ((tmsk | vm[g[cur][i]]) != tmsk)
  51.     ta = (ta + solve(g[cur][i], tmsk | vm[g[cur][i]])) % MOD;
  52.     dp[cur][tmsk] = ta;
  53.   }
  54.   return dp[cur][tmsk];
  55. }
  56.  
  57. int main() {
  58.   scanf("%d", &t);
  59.   while (t --) {
  60.    
  61.     scanf("%d %d %d", &n, &m, &k);
  62.  
  63.     kf = factorize(k);
  64.     kmsk = (1 << (int)kf.size()) - 1;
  65.  
  66.     for (int i = 0; i < n; i ++) {
  67.       scanf("%d\n", &v[i]);
  68.       uf[i] = (k % v[i]) == 0;
  69.       g[i].clear();
  70.       dp[i].clear();
  71.       if (uf[i])
  72.     vm[i] = calc_mask(v[i]);
  73.     }
  74.    
  75.     for (int i = 0; i < m; i ++) {
  76.       scanf("There is a door from room %d to room %d.\n", &a, &b);
  77.       a --; b --;
  78.       if (uf[a] && uf[b])
  79.     g[a].push_back(b);
  80.     }
  81.  
  82.     printf("%d\n", solve(0, vm[0]));
  83.   }
  84.   return 0;
  85. }
RAW Paste Data