fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - Ti20 - THPT chuyên Lương Thế Vinh
  2. /// Training VOI 2023
  3.  
  4. #include<bits/stdc++.h>
  5. //#include <ext/pb_ds/assoc_container.hpp>
  6. //#include <ext/pb_ds/trie_policy.hpp>
  7. //#include <ext/rope>
  8.  
  9. //#pragma GCC optimize("Ofast")
  10. //#pragma GCC optimization("unroll-loops, no-stack-protector")
  11. //#pragma GCC target("avx,avx2,fma")
  12.  
  13. //using namespace std;
  14. //using namespace __gnu_pbds;
  15. //using namespace __gnu_cxx;
  16.  
  17. #define fi first
  18. #define se second
  19. #define TASK "scp"
  20. #define pb push_back
  21. #define EL cout << endl
  22. #define Ti20_ntson int main()
  23. #define in(x) cout << x << endl
  24. #define all(x) (x).begin(),(x).end()
  25. #define getbit(x, i) (((x) >> (i)) & 1)
  26. #define cntbit(x) __builtin_popcount(x)
  27. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  28. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  29. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  30.  
  31. using namespace std;
  32.  
  33. typedef long long ll;
  34. typedef vector<int> vi;
  35. typedef pair<int,int> vii;
  36. typedef unsigned long long ull;
  37. typedef vector<vector<int>> vvi;
  38. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  39.  
  40. const int N = 305;
  41. const int oo = INT_MAX;
  42. const int mod = 1e9 + 7;
  43. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  44. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  45.  
  46. int n, a[N];
  47. ll fact[N], ifact[N];
  48. int dp[N][N];
  49.  
  50. inline void Read_Input() {
  51.     cin >> n;
  52.     FOR(i, 1, n)
  53.         cin >> a[i];
  54. }
  55.  
  56. int Pow(int n, int k) {
  57.     if (k == 0)
  58.         return 1;
  59.     if (k == 1)
  60.         return n;
  61.     int res = Pow(n, k / 2);
  62.     res = 1ll * res * res % mod;
  63.     if (k & 1) res = 1ll * res * n % mod;
  64.     return res;
  65. }
  66.  
  67. int C(int k, int n) {
  68.     if (k > n) return 0;
  69.     return (fact[n] * ifact[n - k] % mod) * ifact[k] % mod;
  70. }
  71.  
  72. inline void Add(int &u, int v) {
  73.     u += v;
  74.     if (u >= mod) u -= mod;
  75. }
  76.  
  77. inline void Solve() {
  78.     fact[0] = 1;
  79.     FOR(i, 1, n)
  80.         fact[i] = fact[i - 1] * i % mod;
  81.     ifact[n] = Pow(fact[n], mod - 2);
  82.     FORD(i, n, 1)
  83.         ifact[i - 1] = ifact[i] * i % mod;
  84.     FOR(i, 1, n)
  85.         for (int j = 2; j * j <= a[i]; j++)
  86.             while (a[i] % (j * j) == 0)
  87.                 a[i] /= (j * j);
  88.     unordered_map<int, int> mp;
  89.     FOR(i, 1, n)
  90.         mp[a[i]]++;
  91.     n = 0;
  92.     for (auto[val, u] : mp)
  93.         a[++n] = u;
  94.     dp[1][a[1] - 1] = fact[a[1]];
  95.     int Sum = a[1];
  96.     FOR(i, 1, n - 1) {
  97.         FOR(j, 0, Sum)
  98.             if (dp[i][j])
  99.                 FOR(k, 0, j)
  100.                     FOR(t, max(1, k), a[i + 1]) {
  101.                         int nj = j - k + a[i + 1] - t;
  102.                         Add(dp[i + 1][nj], 1ll * (1ll * (1ll * (1ll * dp[i][j] * C(t - 1, a[i + 1] - 1) % mod) * fact[a[i + 1]] % mod) *  C(t - k, Sum + 1 - j) % mod) * C(k, j) % mod);
  103.                     }
  104.         Sum += a[i + 1];
  105.     }
  106.     cout << dp[n][0];
  107. }
  108.  
  109. Ti20_ntson {
  110.     freopen(TASK".INP","r",stdin);
  111.     freopen(TASK".OUT","w",stdout);
  112.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  113.     int T = 1;
  114. //    cin >> T;
  115.     while (T -- ) {
  116.         Read_Input();
  117.         Solve();
  118.     }
  119. }
  120.  
  121.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/00OsY9
language:
C++14 (gcc 8.3)
created:
3 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!