Sponsors

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;
}

Regional Lenders Are Merging...

The Consolidation Wave: Why Regional Lenders Are Merging to...

Rush announce reunion tour...

Rush Announces Triumphant Reunion Tour Five Years After Neil...

Partnership turns soggy paddocks...

The Kidney of the Landscape: How Partnerships are Revitalizing...

More CEOs want Elon...

The High-Stakes Gamble: Why 'Moonshot' CEO Pay is Worrying...

I did not expect...

I Did Not Expect This Midrange Sony Soundbar to...

Combination of coaching, personnel...

LSU's Defensive Surge: A Winning Combination of Coaching and...

Regional Lenders Are Merging to Answer the Challenge From Megabanks

The Consolidation Wave: Why Regional Lenders Are Merging to Fight Megabank Dominance The landscape of American banking is undergoing a rapid transformation, characterized by a...

Rush announce reunion tour five years after the death of drummer Neil Peart

Rush Announces Triumphant Reunion Tour Five Years After Neil Peart’s Passing The landscape of progressive rock was irrevocably changed five years ago with the passing...

Partnership turns soggy paddocks into wetlands – and a model for cleaner waterways

The Kidney of the Landscape: How Partnerships are Revitalizing Waterways Through Wetland Creation Wetlands have long been dubbed the 'kidneys of the landscape,' and for...

More CEOs want Elon Musk–style ‘moonshot’ pay packages—but comp experts are raising alarms

The High-Stakes Gamble: Why 'Moonshot' CEO Pay is Worrying Compensation Experts A new, highly ambitious trend is sweeping through corporate boardrooms: the demand for "moonshot"...

I did not expect this midrange Sony soundbar to rival my Sonos system like this

I Did Not Expect This Midrange Sony Soundbar to Rival My Sonos System Sony's Bravia Theater System 6, a mid-range soundbar, has surprisingly impressed reviewers...

Combination of coaching, personnel has LSU’s defense ‘playing great’

LSU's Defensive Surge: A Winning Combination of Coaching and Personnel The LSU Tigers' impressive defensive turnaround hasn't been a matter of luck; it's a strategic...

Disney’s Kimmel suspension shows Trump’s increasing grip over media

Disney’s Kimmel Suspension: Trump’s Tightening Grip on Media? The recent suspension of Jimmy Kimmel from Disney, following controversial comments about former President Trump, has sparked...

New breath sensor detects diabetes quickly and easily

New Breath Sensor Detects Diabetes Quickly and Easily Diabetes affects millions, often going undiagnosed until significant health problems arise. Traditional methods of diagnosis, such...

Family Counseling Expert Barbara Pierce-Morrow of Geneva Explains How School-Based Support Helps Students for HelloNation

School-Based Support: A Key to Student Success In today's challenging educational landscape, students face a multitude of pressures that can significantly impact their academic performance...