fork download
copy 
  1. // #pragma comment(linker, "/stack:200000000")
  2. // #pragma GCC optimize("Ofast")
  3. // #pragma GCC optimize ("unroll-loops")
  4. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // codeforces
  5. //#pragma GCC target("avx,avx2,fma")
  6. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") // yandex
  7.  
  8. #include "bits/stdc++.h"
  9. using namespace std;
  10. #ifndef LOCAL
  11. #define endl '\n'
  12. #endif
  13.  
  14. #define fr(i, a, b) for(int i = a; i <= b; i++)
  15. #define rf(i, a, b) for(int i = a; i >= b; i--)
  16. #define pf push_front
  17. #define pb push_back
  18. #define eb emplace_back
  19. #define fi first
  20. #define se second
  21. #define all(x) x.begin(), x.end()
  22. #define rall(x) x.rbegin(), x.rend()
  23. #define sz(x) (int)x.size()
  24. #define lb lower_bound
  25. #define ub upper_bound
  26.  
  27. typedef long long ll;
  28. typedef long double f80;
  29. typedef pair<int,int> pii;
  30. typedef pair<ll,ll> pll;
  31.  
  32. int pct(int x) { return __builtin_popcount(x); }
  33. int pct(ll x) { return __builtin_popcountll(x); }
  34. int bt(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))
  35. int bt(ll x) { return 63 - __builtin_clzll(x); } // floor(log2(x))
  36. int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
  37. ll cdiv(ll a, ll b) { return a / b + !(a < 0 || a % b == 0); }
  38. int nxt_C(int x) { int c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }
  39. ll nxt_C(ll x) { ll c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }
  40.  
  41. vector<int> get_bits(int mask) {
  42. 	vector<int> bb;
  43. 	while(mask) { int b = bt(mask); bb.pb(b); mask ^= (1 << b); }
  44. 	reverse(all(bb));
  45. 	return bb;
  46. }
  47.  
  48. int get_mask(vector<int> v) {
  49. 	int mask = 0;
  50. 	for(int x : v) { mask ^= (1 << x); }
  51. 	return mask;
  52. }
  53.  
  54. template<typename T>
  55. void uniq(vector<T> &v) { sort(all(v)); v.resize(unique(all(v)) - v.begin()); }
  56.  
  57. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  58.  
  59. ll rand(ll l, ll r){
  60. 	uniform_int_distribution<ll> uid(l, r);
  61. 	return uid(rng);
  62. }
  63.  
  64. void sc() {}
  65.  
  66. template <typename Head, typename... Tail>
  67. void sc(Head &H, Tail &... T) { cin >> H; sc(T...); }
  68.  
  69. #ifdef LOCAL
  70. #define debug(...) cerr << "[L:" << __LINE__ << "][" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  71. #else
  72. #define debug(...) 42
  73. #endif
  74.  
  75. // #ifndef LOCAL
  76. // string to_string(__int128 x) {
  77. // 	string s = "";
  78. // 	bool neg = 0;
  79. // 	if(x < 0) { s += "-"; neg = 1; x = -x; }
  80. // 	if(!x) s += '0';
  81. // 	while(x) {
  82. // 		int rem = x % 10;
  83. // 		s += to_string(rem);
  84. // 		x /= 10;
  85. // 	}
  86. // 	reverse(s.begin() + neg, s.end());
  87. // 	return s;
  88. // }
  89. // #endif
  90.  
  91. const int mod = 1e9 + 7; // 998244353;
  92.  
  93. int pwr(int a,ll b) {
  94. 	int ans = 1;
  95. 	while(b) {
  96. 		if(b & 1) ans = (ans * 1LL * a) % mod;
  97. 		a = (a * 1LL * a) % mod;
  98. 		b >>= 1;
  99. 	}
  100. 	return ans;
  101. }
  102.  
  103. /*
  104. 	Lookout for overflows!!
  105. 	Check array sizes!!
  106. 	Clear before test cases!!
  107. 	Use the correct modulo!!
  108. 	Check for corner cases!!
  109. 	Are you forgetting something?!
  110. 	Read problem statement carefully!!!
  111. */
  112.  
  113. template <typename T>
  114. T inverse(T a, T m) {
  115.   T u = 0, v = 1;
  116.   while (a != 0) {
  117.     T t = m / a;
  118.     m -= t * a; swap(a, m);
  119.     u -= t * v; swap(u, v);
  120.   }
  121.   assert(m == 1);
  122.   return u;
  123. }
  124.  
  125. template <typename T>
  126. class Modular {
  127.  public:
  128.   using Type = typename decay<decltype(T::value)>::type;
  129.  
  130.   constexpr Modular() : value() {}
  131.   template <typename U>
  132.   Modular(const U& x) {
  133.     value = normalize(x);
  134.   }
  135.  
  136.   template <typename U>
  137.   static Type normalize(const U& x) {
  138.     Type v;
  139.     if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
  140.     else v = static_cast<Type>(x % mod());
  141.     if (v < 0) v += mod();
  142.     return v;
  143.   }
  144.  
  145.   const Type& operator()() const { return value; }
  146.   template <typename U>
  147.   explicit operator U() const { return static_cast<U>(value); }
  148.   constexpr static Type mod() { return T::value; }
  149.  
  150.   Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  151.   Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  152.   template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  153.   template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  154.   Modular& operator++() { return *this += 1; }
  155.   Modular& operator--() { return *this -= 1; }
  156.   Modular operator++(int) { Modular result(*this); *this += 1; return result; }
  157.   Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
  158.   Modular operator-() const { return Modular(-value); }
  159.  
  160.   template <typename U = T>
  161.   typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
  162. #ifdef _WIN32
  163.     uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
  164.     uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
  165.     asm(
  166.       "divl %4; \n\t"
  167.       : "=a" (d), "=d" (m)
  168.       : "d" (xh), "a" (xl), "r" (mod())
  169.     );
  170.     value = m;
  171. #else
  172.     value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
  173. #endif
  174.     return *this;
  175.   }
  176.   template <typename U = T>
  177.   typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
  178.     int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
  179.     value = normalize(value * rhs.value - q * mod());
  180.     return *this;
  181.   }
  182.   template <typename U = T>
  183.   typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
  184.     value = normalize(value * rhs.value);
  185.     return *this;
  186.   }
  187.  
  188.   Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
  189.  
  190.   template <typename U>
  191.   friend const Modular<U>& abs(const Modular<U>& v) { return v; }
  192.  
  193.   template <typename U>
  194.   friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
  195.  
  196.   template <typename U>
  197.   friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
  198.  
  199.   template <typename U>
  200.   friend std::istream& operator>>(std::istream& stream, Modular<U>& number);
  201.  
  202.  private:
  203.   Type value;
  204. };
  205.  
  206. template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
  207. template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
  208. template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }
  209.  
  210. template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
  211. template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
  212. template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
  213.  
  214. template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }
  215.  
  216. template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
  217. template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
  218. template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
  219.  
  220. template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
  221. template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
  222. template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
  223.  
  224. template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
  225. template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
  226. template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
  227.  
  228. template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
  229. template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
  230. template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
  231.  
  232. template<typename T, typename U>
  233. Modular<T> power(const Modular<T>& a, const U& b) {
  234.   assert(b >= 0);
  235.   Modular<T> x = a, res = 1;
  236.   U p = b;
  237.   while (p > 0) {
  238.     if (p & 1) res *= x;
  239.     x *= x;
  240.     p >>= 1;
  241.   }
  242.   return res;
  243. }
  244.  
  245. template <typename T>
  246. bool IsZero(const Modular<T>& number) {
  247.   return number() == 0;
  248. }
  249.  
  250. template <typename T>
  251. string to_string(const Modular<T>& number) {
  252.   return to_string(number());
  253. }
  254.  
  255. template <typename T>
  256. std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  257.   return stream << number();
  258. }
  259.  
  260. template <typename T>
  261. std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  262.   typename common_type<typename Modular<T>::Type, int64_t>::type x;
  263.   stream >> x;
  264.   number.value = Modular<T>::normalize(x);
  265.   return stream;
  266. }
  267.  
  268. /*
  269. using ModType = int;
  270.  
  271. struct VarMod { static ModType value; };
  272. ModType VarMod::value;
  273. ModType& md = VarMod::value;
  274. using Mint = Modular<VarMod>;
  275.  
  276. */
  277.  
  278. constexpr int md = 1e9 + 7;
  279. using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
  280.  
  281. Mint pwr(Mint a, ll k) {
  282. 	Mint ans = 1;
  283. 	while(k) {
  284. 		if(k & 1) ans = ans * a;
  285. 		a = a * a;
  286. 		k >>= 1;
  287. 	}
  288. 	return ans;
  289. }
  290.  
  291. const int N = 55;
  292. Mint dp[N][N][N][N];
  293. Mint ans[N][N];
  294.  
  295. void solve() {
  296.     fr(i, 1, N - 1) {
  297.         fr(j, 1, i) {
  298.             fr(k, 1, i) {
  299.                 fr(l, k, i) {
  300.                     dp[i][j][k][l] = 0;
  301.                 }
  302.             }
  303.         }
  304.     }
  305.     dp[1][1][1][1] = 1;
  306.     fr(i, 1, N - 2) {
  307.         fr(j, 1, i) {
  308.             fr(k, 1, i) {
  309.                 fr(l, k, i) {
  310.                     Mint val = dp[i][j][k][l];
  311.                     ans[i][l] += val;
  312.                     fr(m, j + 1, i + 1) {
  313.                         dp[i + 1][m][k + 1][max(k + 1, l)] += val;
  314.                     }
  315.                     fr(m, 1, j) {
  316.                         dp[i + 1][m][1][l] += val;
  317.                     }
  318.                 }
  319.             }
  320.         }
  321.     }
  322.     int t;
  323.     sc(t);
  324.     while(t--) {
  325.         int n, k;
  326.         sc(n, k);
  327.         cout << ans[n][k] << endl;
  328.     }
  329. }
  330.  
  331. int main() {
  332. 	ios :: sync_with_stdio(0);
  333. 	cin.tie(0);
  334. 	cout.tie(0);
  335. 	int t = 1;
  336. 	// cin >> t;
  337. 	for(int tt = 1; tt <= t; tt++) {
  338. 		solve();
  339. 	}
  340. 	return 0;
  341. }
Success #stdin #stdout 0.06s 19180KB
comments (?)
stdin
copy 
4
9 4
9 3
7 1
7 7
stdout
copy 
60875
189524
1
1
https://ideone.com/UZ0DXy
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!