Codeforces Round #429 (Div. 2), problem: (E) On the Bench Solution In C/C++

#include<bits/stdc++.h>
#define ll long long int
#define LL long long int
#define ULL unsigned long long int
#define sf(a) scanf(“%d”,&a)
#define sl(a) scanf(“%lld”,&a)
#define fr first
#define sc second
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vll vector<LL>
#define vpii vector<pii>
#define rep1(a,b) for(int a=1;a<=b;a++)
#define rep2(a,b) for(int a=0;a<b;a++)
#define CLR(a,b) memset(a,b,sizeof(a))
#define Clear(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define LSOne(S) (S&(-S))
#define all(a) a.begin(),a.end()
#define Prime 31
using namespace std;
#define maxn 200100
#define INF 1ll<<62
#define mMax 20005
#define nMax 2505
#define SZ(a) a.size()
LL ar1[305];
class UnionFind { // OOP style
private:
vi p, rank, setSize; // remember: vi is vector<int>
int numSets;
public:
UnionFind(int N) {
setSize.assign(N, 1); numSets = N; rank.assign(N, 0);
p.assign(N, 0); for (int i = 0; i < N; i++) p[i] = i; }
int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
void unionSet(int i, int j) {
if (!isSameSet(i, j)) { numSets–;
int x = findSet(i), y = findSet(j);
// rank is used to keep the tree short
if (rank[x] > rank[y]) { p[y] = x; setSize[x] += setSize[y]; }
else { p[x] = y; setSize[y] += setSize[x];
if (rank[x] == rank[y]) rank[y]++; } } }
int numDisjointSets() { return numSets; }
int sizeOfSet(int i) { return setSize[findSet(i)]; }
};
LL bigmod(LL a,LL p)
{
if(p==1) return a%mod;
if(p%2) return (a*bigmod(a,p-1))%mod;
LL c=bigmod(a,p/2);
return (c*c)%mod;
}
LL factn[1000],invfactn[1000];
LL factm[1000],invfactm[1000];
void init(int n)
{
factn[0]=1;
invfactn[0]=1;
for(LL i=1;i<=n;i++) factn[i]=(factn[i-1]*i)%mod;
for(LL i=1;i<=n;i++) invfactn[i]=(invfactn[i-1]*bigmod(i,mod-2))%mod;
return ;
}
void init2(int n)
{
factm[0]=1;
invfactm[0]=1;
for(LL i=1;i<=n;i++) factm[i]=(factm[i-1]*i)%mod;
for(LL i=1;i<=n;i++) invfactm[i]=(invfactm[i-1]*bigmod(i,mod-2))%mod;
return ;
}
LL nCr(int n,int r)
{
if(n<0) return 0;
if(n<r) return 0;
LL res=(invfactn[n-r]*invfactn[r])%mod;
res=(res*factn[n])%mod;
return res;
}
LL nPr2(int n,int r)
{
LL res=(invfactm[n-r])%mod;
res=(res*factm[n])%mod;
return res;
}
vi vec1;
LL dp[305][305];
LL call(int i,int bad,int n,int total)
{
if(i==n) return (bad==0);
LL &ret=dp[i][bad];
if(ret!=-1) return ret;
ret=0;
int cur_total=total+vec1[i];
int gaps=total+1;
for(int split=1;split<= min(gaps,vec1[i]);split++)
{
for(int chosen_bad_gap=0;chosen_bad_gap<=min(bad,split);chosen_bad_gap++)
{
int good_gaps=gaps-chosen_bad_gap;
int new_bad= bad-chosen_bad_gap+vec1[i]-split;
int good_splits=split-chosen_bad_gap;
LL temp=1;
temp= (nCr(vec1[i]-1,split-1)*factn[vec1[i]])%mod;
temp = (temp*nCr(bad,chosen_bad_gap))%mod;
temp = (temp* nCr(gaps-bad,good_splits) )%mod;
temp = (temp* call(i+1,new_bad,n,total+vec1[i]))%mod;
ret = (ret+temp)%mod;
}
}
return ret;
}
int main()
{
#ifdef shakil
freopen(“input.txt”,”r”,stdin);
//freopen(“output.txt”,”w”,stdout);
#endif
map<int,int> Map;
int n,k;
cin>>n;
for(int i=0;i<n;i++) {scanf(“%d”,&ar1[i]);Map[ar1[i]]++;}
UnionFind uf(n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
double a=sqrt(ar1[i]*ar1[j]);
if(floor(a)==ceil(a))
uf.unionSet(i,j);
}
init(n+2);
int s=uf.numDisjointSets();
set<int> S;
for(int i=0;i<n;i++) S.insert(uf.findSet(i));
vi x;
for(set<int>::iterator it=S.begin();it!=S.end();it++) x.pb(*it);
for(int i=0;i<x.size();i++) vec1.pb(uf.sizeOfSet(x[i]));
CLR(dp,-1);
LL res=call(0,0,x.size(),0);
//for(map<int,int>::iterator it=Map.begin();it!=Map.end();it++) res= (res*invfactn[it->sc])%mod;
printf(“%lld\n”,res);
return 0;
}