fork download
  1. # include <bits/stdc++.h>
  2. using namespace std;
  3. # define fi cin
  4. # define fo cout
  5. # define x first
  6. # define y second
  7. # define ll long long
  8. # define db long double
  9. # define scn(x) scanf("%I64d",&x)
  10. # define scan(x) scanf("%d",&x)
  11. # define print(x) printf("%d ",x)
  12. # define prnt(x) printf("%I64d ",x);
  13. # define eol printf("\n")
  14. # define IOS ios_base :: sync_with_stdio(0)
  15. # define pe "Possible"
  16. # define ie "Impossible"
  17. # define halt(...) {fo << (__VA_ARGS__) << '\n';exit(0);}
  18. # define rep1(n) for (int qwerty = 1;qwerty <= n;++qwerty)
  19. # define pp(n) cerr << #n << " = " << n << '\n'
  20. # define ppp(v) for (auto it : v) cerr << it << ' ';cerr << '\n'
  21. # define aprint(x,y,z) for (int i = x;i <= y;++i) cerr << z[i] << ' ';cerr << '\n'
  22. # define rep(n) for (int i = 1;i <= n;++i)
  23. const int mod = 1e9 + 7;
  24. ll dp[1 << 19][19];
  25. vector < int > s[55];
  26. int Log[1 << 20];
  27. int v[55][55];
  28. int main(void)
  29. {
  30. #ifdef CF
  31. ifstream fi("input");
  32. #endif // CF
  33. srand(time(0));
  34. fo << fixed << setprecision(7);
  35. cerr << fixed << setprecision(7);
  36. int n,m;
  37. fi>>n>>m;
  38. rep1(m)
  39. {
  40. int a,b;
  41. fi>>a>>b;
  42. --a;--b;
  43. v[a][b] = v[b][a] = 1;
  44. s[a].push_back(b);
  45. s[b].push_back(a);
  46. }
  47. for (int i = 2;i <= 1e6;++i) Log[i] = Log[i/2] + 1;
  48. for (int i = 0;i < n;++i) dp[1 << i][i] = 1;
  49. for (int mask = 1;mask < (1 << n);++mask)
  50. if (__builtin_popcount(mask) > 1)
  51. {
  52. for (int i = 0;i < n;++i)
  53. if (((mask >> i)&1) && i != Log[mask & (-mask)])
  54. for (auto it : s[i])
  55. if ((mask >> it)&1)
  56. dp[mask][i] += dp[mask ^ (1 << i)][it];
  57. }
  58. ll ans = 0;
  59. for (int mask = 1;mask < (1 << n);++mask)
  60. for (int i = 0;i < n;++i)
  61. if (__builtin_popcount(mask) >= 3 && (((mask >> i)&1)) && v[Log[mask&(-mask)]][i])
  62. ans += dp[mask][i];
  63. ans /= 2;
  64. fo << ans << '\n';
  65. return 0;
  66. }
  67.  
  68.  
  69.  
Success #stdin #stdout 0s 85376KB
stdin
Standard input is empty
stdout
0