fork download
copy 
  1. #include <cassert>
  2. #include <cmath>
  3. #include <cstdint>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cstring>
  7. #include <algorithm>
  8. #include <bitset>
  9. #include <complex>
  10. #include <deque>
  11. #include <functional>
  12. #include <iostream>
  13. #include <map>
  14. #include <numeric>
  15. #include <queue>
  16. #include <set>
  17. #include <sstream>
  18. #include <string>
  19. #include <unordered_map>
  20. #include <unordered_set>
  21. #include <utility>
  22. #include <vector>
  23.  
  24. using namespace std;
  25.  
  26. using Int = long long;
  27.  
  28. template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
  29. template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
  30. template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
  31. template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
  32.  
  33.  
  34. template <unsigned M_> struct ModInt {
  35.   static constexpr unsigned M = M_;
  36.   unsigned x;
  37.   constexpr ModInt() : x(0) {}
  38.   constexpr ModInt(unsigned x_) : x(x_ % M) {}
  39.   constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  40.   constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  41.   constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  42.   ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  43.   ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  44.   ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  45.   ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  46.   ModInt pow(long long e) const {
  47.     if (e < 0) return inv().pow(-e);
  48.     ModInt a = *this, b = 1; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  49.   }
  50.   ModInt inv() const {
  51.     unsigned a = M, b = x; int y = 0, z = 1;
  52.     for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
  53.     assert(a == 1); return ModInt(y);
  54.   }
  55.   ModInt operator+() const { return *this; }
  56.   ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0; return a; }
  57.   ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  58.   ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  59.   ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  60.   ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  61.   template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  62.   template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  63.   template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  64.   template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  65.   explicit operator bool() const { return x; }
  66.   bool operator==(const ModInt &a) const { return (x == a.x); }
  67.   bool operator!=(const ModInt &a) const { return (x != a.x); }
  68.   friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
  69. };
  70.  
  71. constexpr unsigned MO = 1000000007;
  72. using Mint = ModInt<MO>;
  73.  
  74.  
  75. constexpr int LIM = 110;
  76. Mint inv[LIM], fac[LIM], invFac[LIM];
  77.  
  78. void prepare() {
  79.   inv[1] = 1;
  80.   for (int i = 2; i < LIM; ++i) {
  81.     inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
  82.   }
  83.   fac[0] = invFac[0] = 1;
  84.   for (int i = 1; i < LIM; ++i) {
  85.     fac[i] = fac[i - 1] * i;
  86.     invFac[i] = invFac[i - 1] * inv[i];
  87.   }
  88. }
  89. Mint binom(Int n, Int k) {
  90.   if (0 <= k && k <= n) {
  91.     assert(n < LIM);
  92.     return fac[n] * invFac[k] * invFac[n - k];
  93.   } else {
  94.     return 0;
  95.   }
  96. }
  97.  
  98.  
  99. template <class T> vector<vector<T>> zeta(const vector<T> &as) {
  100.   const int n = __lg(as.size());
  101.   assert(static_cast<int>(as.size()) == 1 << n);
  102.   vector<vector<T>> zas(1 << n, vector<T>(n + 1, 0));
  103.   for (int h = 0; h < 1 << n; ++h) zas[h][__builtin_popcount(h)] = as[h];
  104.   for (int i = 0; i < n; ++i) for (int h = 0; h < 1 << n; ++h) {
  105.     if (!(h & 1 << i)) {
  106.       for (int k = 0; k <= n; ++k) zas[h | 1 << i][k] += zas[h][k];
  107.     }
  108.   }
  109.   return zas;
  110. }
  111.  
  112. template <class T> vector<T> moebius(vector<vector<T>> zas) {
  113.   const int n = zas[0].size() - 1;
  114.   assert(static_cast<int>(zas.size()) == 1 << n);
  115.   for (int i = 0; i < n; ++i) for (int h = 0; h < 1 << n; ++h) {
  116.     if (!(h & 1 << i)) {
  117.       for (int k = 0; k <= n; ++k) zas[h | 1 << i][k] -= zas[h][k];
  118.     }
  119.   }
  120.   vector<T> as(1 << n);
  121.   for (int h = 0; h < 1 << n; ++h) as[h] = zas[h][__builtin_popcount(h)];
  122.   return as;
  123. }
  124.  
  125.  
  126. vector<Mint> mul(const vector<Mint> &as, const vector<Mint> &bs) {
  127.   const int n = as.size() - 1;
  128.   vector<Mint> cs(n + 1, 0);
  129.   for (int i = 0; i <= n; ++i) for (int j = 0; i + j <= n; ++j) {
  130.     cs[i + j] += as[i] * bs[j];
  131.   }
  132.   return cs;
  133. }
  134. vector<Mint> power(const vector<Mint> &as, Mint e) {
  135.   /*
  136.     b = a^e
  137.     b' / b = e a' / a
  138.     a b' = e a' b
  139.   */
  140.   const int n = as.size() - 1;
  141.   assert(as[0].x == 1);
  142.   vector<Mint> bs(n + 1, 0);
  143.   bs[0] = 1;
  144.   for (int i = 1; i <= n; ++i) {
  145.     Mint sum = 0;
  146.     for (int j = 1; j <= i; ++j) sum += ((e + 1) * j - i) * as[j] * bs[i - j];
  147.     bs[i] = inv[i] * sum;
  148.   }
  149.   return bs;
  150. }
  151.  
  152.  
  153. int uf[LIM];
  154. int root(int u) {
  155.   return (uf[u] < 0) ? u : (uf[u] = root(uf[u]));
  156. }
  157. bool connect(int u, int v) {
  158.   u = root(u);
  159.   v = root(v);
  160.   if (u == v) return false;
  161.   if (uf[u] > uf[v]) swap(u, v);
  162.   uf[u] += uf[v];
  163.   uf[v] = u;
  164.   return true;
  165. }
  166.  
  167.  
  168. struct UnluckyNumber {
  169.   int numberOfColourings(int n, int m, int k, int z, vector <int> x, vector <int> y) {
  170.     prepare();
  171.  
  172.     for (int i = 0; i < m; ++i) {
  173.       --x[i];
  174.       --y[i];
  175.     }
  176.  
  177.     const Int numSelfs = (z % 2 == 0) ? 1 : 0;
  178.     const Int numPairs = ((min(z - 2, 2 * k - z) + 1) - numSelfs) / 2;
  179.     const Int numOthers = k - 2 * numPairs - numSelfs;
  180.  
  181.     // two colors which cannot be adjacent
  182.     vector<Mint> fs(1 << n, 0);
  183.     for (int p = 0; p < 1 << n; ++p) {
  184.       fill(uf, uf + n, -1);
  185.       for (int i = 0; i < m; ++i) {
  186.         if ((p & 1 << x[i]) && (p & 1 << y[i])) {
  187.           connect(x[i], y[i]);
  188.         }
  189.       }
  190.       fs[p] = 1;
  191.       for (int u = 0; u < n; ++u) {
  192.         if (p & 1 << u) {
  193.           if (uf[u] < 0) {
  194.             fs[p] *= 2;
  195.           }
  196.         }
  197.       }
  198.     }
  199.  
  200.     // independent set
  201.     vector<Mint> gs(1 << n, 0);
  202.     for (int p = 0; p < 1 << n; ++p) {
  203.       bool ok = true;
  204.       for (int i = 0; i < m; ++i) {
  205.         ok = ok && !((p & 1 << x[i]) && (p & 1 << y[i]));
  206.       }
  207.       if (ok) {
  208.         gs[p] += 1;
  209.       }
  210.     }
  211.  
  212.     // any
  213.     vector<Mint> hs(1 << n, 1);
  214.  
  215.     // f^numPairs g^numSelfs h^numOthers
  216.     auto zfs = zeta(fs);
  217.     auto zgs = zeta(gs);
  218.     auto zhs = zeta(hs);
  219.     for (int p = 0; p < 1 << n; ++p) {
  220.       zfs[p] = mul(mul(power(zfs[p], numPairs), power(zgs[p], numSelfs)), power(zhs[p], numOthers));
  221.     }
  222.     const auto res = moebius(zfs);
  223.  
  224.     const Mint ans = res[(1 << n) - 1];
  225.     return ans.x;
  226.   }
  227. };
  228.  
  229.  
  230. int brute(int n, int m, int k, int z, vector <int> x, vector <int> y) {
  231.   int ans = 0;
  232.   for (int p = 0; p < 1 << (3 * n); ++p) {
  233.     vector<int> col(n);
  234.     for (int u = 0; u < n; ++u) {
  235.       col[u] = ((p >> (3 * u)) & 7) + 1;
  236.     }
  237.     bool ok = true;
  238.     for (int u = 0; u < n; ++u) {
  239.       ok = ok && (1 <= col[u] && col[u] <= k);
  240.     }
  241.     for (int i = 0; i < m; ++i) {
  242.       ok = ok && (col[x[i] - 1] + col[y[i] - 1] != z);
  243.     }
  244.     if (ok) {
  245.       ++ans;
  246.     }
  247.   }
  248.   return ans;
  249. }
  250.  
  251. int main() {
  252.   cout << UnluckyNumber().numberOfColourings(3, 3, 4, 4, {1, 2, 3}, {2, 3, 1}) << endl;
  253.   cout << UnluckyNumber().numberOfColourings(18, 18, 987654321, 1000000000, {1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 16, 17}, {2, 3, 1, 5, 6, 7, 4, 9, 10, 11, 12, 10, 11, 12, 11, 12, 17, 18}) << endl;
  254.  
  255.   /*
  256.   for (int n = 2; n <= 5; ++n) {
  257.     for (int k = 1; k <= 8; ++k) {
  258.       for (int z = 2; z <= 2 * k; ++z) {
  259.         cerr << "n = " << n << ", k = " << k << ", z = " << z << " ..." << endl;
  260.         for (int p = 0; p < 1 << (n * (n - 1) / 2); ++p) {
  261.           vector<int> x, y;
  262.           int pos = 0;
  263.           for (int u = 0; u < n; ++u) for (int v = u + 1; v < n; ++v) {
  264.             if (p & 1 << pos) {
  265.               x.push_back(u + 1);
  266.               y.push_back(v + 1);
  267.             }
  268.             ++pos;
  269.           }
  270.           int m = x.size();
  271.           const int brt = brute(n, m, k, z, x, y);
  272.           const int res = UnluckyNumber().numberOfColourings(n, m, k, z, x, y);
  273.           if (brt != res) {
  274.             cerr << "n = " << n << ", m = " << m << ", k = " << k << ", z = " << z << endl;
  275.             cerr << "x = "; pv(x.begin(), x.end());
  276.             cerr << "y = "; pv(y.begin(), y.end());
  277.             cerr << "brt = " << brt << endl;
  278.             cerr << "res = " << res << endl;
  279.             assert(false);
  280.           }
  281.         }
  282.       }
  283.     }
  284.   }
  285.   */
  286.   return 0;
  287. }
  288.  
Success #stdin #stdout 2.01s 130148KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
36
409052991
https://ideone.com/r2HnIX
language:
C++14 (gcc 8.3)
created:
3 years 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!