Saturday, May 25, 2024

# 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(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++)
{
{
LL temp=1;
temp= (nCr(vec1[i]-1,split-1)*factn[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;
}

## Celebrating Black History Month:...

As February unfolds, so does the annual celebration of...

## The Path to Self-Mastery:...

Embarking on a journey of self-mastery and breaking free...

## Wizards of Waverly Place...

In a spellbinding announcement, Disney has officially revealed that...

## Jim Irsay’s Reported ‘Suspected...

In a shocking turn of events last month, Jim...

Coachella Valley Music and Arts Festival, one of the...

## 2024 Taiwan Election: Pivotal...

As Taiwan gears up for its 2024 presidential election,...

### Celebrating Black History Month: Past, Future

As February unfolds, so does the annual celebration of Black History Month, a time to reflect on the profound contributions, resilience, and rich cultural...

### The Path to Self-Mastery: Lessons from Book ‘The Mountain Is You’

Embarking on a journey of self-mastery and breaking free from self-sabotage is a transformative process that requires dedication and conscious effort. Brianna Wiest's insightful...

### Wizards of Waverly Place Cast Reunites for Enchanting Revival

In a spellbinding announcement, Disney has officially revealed that the beloved fantasy series "Wizards of Waverly Place" is set for a magical comeback, featuring...

### Jim Irsay’s Reported ‘Suspected Overdose’: A Closer Look

In a shocking turn of events last month, Jim Irsay, the owner of the Indianapolis Colts, was reportedly found unresponsive at his home in...

### Coachella 2024: Iconic headliners, unforgettable musical experience!

Coachella Valley Music and Arts Festival, one of the most iconic and eagerly anticipated music festivals globally, has just dropped its highly anticipated lineup...

### 2024 Taiwan Election: Pivotal Moment in Political Landscape

As Taiwan gears up for its 2024 presidential election, the political landscape is buzzing with anticipation and fervor. With the island nation situated at...

### Michael Strahan’s Daughter’s Medulloblastoma Diagnosis

In a recent and heartbreaking revelation, Michael Strahan, former NFL star and television personality, shared the devastating news of his daughter Isabella's diagnosis with...

### Michigan vs. Washington: The 2024 National Championship Clash

In a highly anticipated matchup, the 2024 National Championship will witness a clash of football titans as the Michigan Wolverines square off against the...

### Jason Kelce: Unmasking the Unconventional NFL Icon

In the world of professional football, where conformity often takes center stage, one player stands out as a beacon of individuality, both on and...