fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int mod = 1e9 + 7, maxn = 201, maxm = 11, maxmask = 1 << 11;
  5.  
  6. int n, m, s, dm[maxm][maxn], ds[maxm] = {0}, did[maxn][maxm] = {0};
  7. bool dl[maxn][maxn] = {false};
  8.  
  9. long long** T[maxm][maxm];
  10. long long** tsp[maxmask][maxm];
  11.  
  12. long long cw[maxmask] = {0}, dp[maxmask] = {0};
  13.  
  14. void ngat(long long** mat, int r)
  15. {
  16.     if (!mat) return;
  17.     for (int i = 0; i < r; ++i) delete[] mat[i];
  18.     delete[] mat;
  19. }
  20.  
  21. long long** mul(long long** a, int r1, int c1, long long** b, int r2, int c2)
  22. {
  23.     if (!a || !b || c1 != r2) return nullptr;
  24.     long long** res = new long long*[r1];
  25.     for (int i = 0; i < r1; ++i) res[i] = new long long[c2]();
  26.  
  27.     for (int i = 0; i < r1; ++i)
  28.     {
  29.         for (int j = 0; j < c2; ++j)
  30.         {
  31.             for (int k = 0; k < c1; ++k)
  32.             {
  33.                 res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod;
  34.             }
  35.         }
  36.     }
  37.     return res;
  38. }
  39.  
  40. void add(long long**& a, int r, int c, long long** b)
  41. {
  42.     if (!b) return;
  43.     if (!a)
  44.     {
  45.         a = b;
  46.         return;
  47.     }
  48.     for (int i = 0; i < r; ++i)
  49.     {
  50.         for (int j = 0; j < c; ++j)
  51.         {
  52.             a[i][j] = (a[i][j] + b[i][j]) % mod;
  53.         }
  54.     }
  55.     ngat(b, r);
  56. }
  57.  
  58. long long trace(long long** mat, int sz)
  59. {
  60.     if (!mat) return 0;
  61.     long long t = 0;
  62.     for (int i = 0; i < sz; ++i) t = (t + mat[i][i]) % mod;
  63.     return t;
  64. }
  65.  
  66. int main()
  67. {
  68.     ios::sync_with_stdio(0);
  69.     cin.tie(0);
  70.     cout.tie(0);
  71.     if(fopen("company.inp","r"))
  72.     {
  73.         freopen("company.inp","r",stdin);
  74.         freopen("company.out","w",stdout);
  75.     }
  76.  
  77.     cin >> n >> m >> s;
  78.  
  79.     for (int i = 0; i < n; ++i)
  80.     {
  81.         int d;
  82.         cin >> d;
  83.         --d;
  84.         dm[d][ds[d]++] = i;
  85.     }
  86.     for (int k = 0; k < s; ++k)
  87.     {
  88.         int u, v;
  89.         cin >> u >> v;
  90.         --u;
  91.         --v;
  92.         dl[u][v] = true;
  93.     }
  94.  
  95.     for (int i = 0; i < n; ++i)
  96.     {
  97.         for (int j = 0; j < m; ++j)
  98.         {
  99.             for (int k = 0; k < ds[j]; ++k)
  100.             {
  101.                 if (dl[i][dm[j][k]]) did[i][j]++;
  102.             }
  103.         }
  104.     }
  105.  
  106.     for (int i = 0; i < m; ++i)
  107.     {
  108.         for (int j = 0; j < m; ++j)
  109.         {
  110.             if (i == j || ds[i] == 0 || ds[j] < 2) continue;
  111.             int si = ds[i], sj = ds[j];
  112.             T[i][j] = new long long*[si];
  113.             for(int k=0; k<si; ++k) T[i][j][k] = new long long[sj]();
  114.  
  115.             int th = (sj - 1) / 2;
  116.             for (int ui = 0; ui < si; ++ui)
  117.             {
  118.                 int u = dm[i][ui];
  119.                 for (int vi = 0; vi < sj; ++vi)
  120.                 {
  121.                     int v = dm[j][vi];
  122.                     if (did[u][j] - dl[u][v] <= th)
  123.                     {
  124.                         T[i][j][ui][vi] = 1;
  125.                     }
  126.                 }
  127.             }
  128.         }
  129.     }
  130.  
  131.     for(int i = 0; i < m; ++i)
  132.     {
  133.         int sz = ds[i];
  134.         if (sz > 0)
  135.         {
  136.             tsp[1 << i][i] = new long long*[sz];
  137.             for(int k=0; k<sz; ++k)
  138.             {
  139.                 tsp[1 << i][i][k] = new long long[sz]();
  140.                 tsp[1 << i][i][k][k] = 1;
  141.             }
  142.         }
  143.     }
  144.  
  145.     for (int mask = 1; mask < (1 << m); ++mask)
  146.         for (int j = 0; j < m; ++j)
  147.         {
  148.             if (!((mask >> j) & 1) || !tsp[mask][j]) continue;
  149.             for (int k = 0; k < m; ++k)
  150.             {
  151.                 if ((mask >> k) & 1) continue;
  152.                 long long** res = mul(tsp[mask][j], ds[__builtin_ctz(mask)], ds[j], T[j][k], ds[j], ds[k]);
  153.                 if(res) add(tsp[mask | (1 << k)][k], ds[__builtin_ctz(mask)], ds[k], res);
  154.             }
  155.         }
  156.     for (int mask = 1; mask < (1 << m); ++mask)
  157.     {
  158.         if (__builtin_popcount(mask) < 2) continue;
  159.         int st = __builtin_ctz(mask);
  160.         for (int en = 0; en < m; ++en)
  161.         {
  162.             if (st != en && ((mask >> en) & 1))
  163.             {
  164.                 long long** res = mul(tsp[mask][en], ds[st], ds[en], T[en][st], ds[en], ds[st]);
  165.                 if (res)
  166.                 {
  167.                     cw[mask] = (cw[mask] + trace(res, ds[st])) % mod;
  168.                     ngat(res, ds[st]);
  169.                 }
  170.             }
  171.         }
  172.     }
  173.  
  174.     dp[0] = 1;
  175.     for (int mask = 1; mask < (1 << m); ++mask)
  176.     {
  177.         int st = __builtin_ctz(mask);
  178.         for (int sub = mask ^ (1 << st); ; sub = (sub - 1) & (mask ^ (1 << st)))
  179.         {
  180.             int cm = sub | (1 << st);
  181.             dp[mask] = (dp[mask] + cw[cm] * dp[mask ^ cm]) % mod;
  182.             if (sub == 0) break;
  183.         }
  184.     }
  185.  
  186.     cout << dp[(1 << m) - 1] << endl;
  187.  
  188.     for (int i = 0; i < m; ++i)
  189.         for (int j = 0; j < m; ++j)
  190.             ngat(T[i][j], ds[i]);
  191.     for (int i = 0; i < (1 << m); ++i)
  192.         for (int j = 0; j < m; ++j)
  193.             if(tsp[i][j]) ngat(tsp[i][j], ds[__builtin_ctz(i)]);
  194.  
  195.     return 0;
  196. }
  197.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/51LnOG
language:
C++14 (gcc 8.3)
created:
2 days 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!