fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define BIT(mask, i) (mask & (1 << (i)))
  5. #define ONBIT(mask, i) (mask | (1 << (i)))
  6.  
  7. const int MAXN = 215;
  8. const int MOD  = 1e9 + 7;
  9.  
  10. int N, M, S;
  11. vector<int> g[MAXN];
  12. int A[MAXN], dem[MAXN], tmp[MAXN][MAXN], check[MAXN][MAXN], cnt[MAXN][MAXN];
  13. int dp[(1 << 10) + 15][215][215];
  14.  
  15. int solve(int mask, int i, int j) {
  16.     if (__builtin_popcount(mask) == M) return 1;
  17.     if (dp[mask][i][j] != -1) return dp[mask][i][j];
  18.  
  19.     int cur = 0;
  20.  
  21.     if (A[i] == A[j]) {
  22.         if (BIT(mask, A[i] - 1)) {
  23.             for (int bit = 0; bit < M; bit++) {
  24.                 if (BIT(mask, bit)) continue;
  25.                 for (auto v : g[bit + 1]) {
  26.                     cur += solve(mask, v, v);
  27.                     cur %= MOD;
  28.                 }
  29.             }
  30.         }
  31.         else {
  32.             for (int bit = 0; bit < M; bit++) {
  33.                 if (BIT(mask, bit) || bit == A[i] - 1) continue;
  34.                 for (auto v : g[bit + 1]) {
  35.                     if (check[j][v]) {
  36.                         cur += solve(ONBIT(mask, bit), i, v);
  37.                         cur %= MOD;
  38.                     }
  39.                 }
  40.             }
  41.         }
  42.     }
  43.     if (A[i] != A[j]) {
  44.         for (int bit = 0; bit < M; bit++) {
  45.             if (BIT(mask, bit) || bit == A[i] - 1) continue;
  46.             for (auto v : g[bit + 1]) {
  47.                 if (check[j][v]) {
  48.                     cur += solve(ONBIT(mask, bit), i, v);
  49.                     cur %= MOD;
  50.                 }
  51.             }
  52.         }
  53.         cur += solve(ONBIT(mask, A[i] - 1), i, i);
  54.     }
  55.  
  56.  
  57.     return dp[mask][i][j] = cur;
  58. }
  59.  
  60.  
  61. signed main() {
  62.     ios_base::sync_with_stdio(0);
  63.     cin.tie(0);
  64.     cout.tie(0);
  65.  
  66. //    freopen("d5companyt.inp", "r", stdin);
  67. //    freopen("d5companyt.out", "w", stdout);
  68.  
  69.     cin >> N >> M >> S;
  70.     for (int i = 1; i <= N; i++) {
  71.         cin >> A[i];
  72.         dem[A[i]]++;
  73.         g[A[i]].push_back(i);
  74.     }
  75.  
  76.     for (int i = 1; i <= S; i++) {
  77.         int a, b;
  78.         cin >> a >> b;
  79.         tmp[a][b] = true;
  80.         cnt[A[a]][b]++;
  81.     }
  82.  
  83.     for (int i = 1; i <= M; i++) {
  84.         for (int j = 1; j <= M; j++) {
  85.             if (i == j) continue;
  86.             for (auto a : g[i]) {
  87.                 for (auto b : g[j]) {
  88.                     if (cnt[j][a] - tmp[b][a] > (dem[j] - 1) / 2) continue;
  89.                     if (cnt[i][b] - tmp[a][b] > (dem[i] - 1) / 2) continue;
  90.                     check[a][b] = true;
  91.                 }
  92.             }
  93.         }
  94.     }
  95.  
  96.  
  97.     memset(dp, -1, sizeof dp);
  98.  
  99.     int ans = 0;
  100.  
  101.     for (auto v : g[A[1]]) {
  102.         ans += solve(0, v, v);
  103.         ans %= MOD;
  104.     }
  105.  
  106.     cout << ans;
  107. }
  108.  
Success #stdin #stdout 0.06s 378828KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0zft1O
language:
C++14 (gcc 8.3)
created:
16 hours 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!