ProgrammingC/C++

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

Read More
Admin
Admin
1003
0

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

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

Previous article
Codeforces Round #429 (Div. 2), problem: (D) Leha and another game about graph Solution In C/C++
Next article
Codeforces Round #429 (Div. 1), problem: (D) Destiny Solution In C/C++
Admin
Admin

More from author

Entertainment

Supernatural: Wayward Special #1 Preview: Winchesters Split Up

Fans of the long-running television phenomenon Supernatural are in for a fresh dose of nostalgia and hunter drama with the...
Admin -
Read
Shopping

The Real Truth About Viral Kitchen Gadgets Before You Buy

📢 As an Amazon Associate, I earn from qualifying purchases.If you had told me six months ago that a single...
Admin -
Read
News

Bird flu could devastate Macquarie Island. Why are we removing the scientists we need to understand it?

Macquarie Island, a remote sub-Antarctic wildlife haven situated midway between Tasmania and Antarctica, is confronting an imminent ecological crisis. As...
Admin -
Read

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Related posts

C/C++

Reject Modernity, Return to 80s, Learn C.

In an era dominated by high-level frameworks, drag-and-drop builders, and AI-assisted coding, a surprising trend is emerging among the youngest...
Admin -
Advertismentspot_img

Latest posts

Supernatural: Wayward Special #1 Preview: Winchesters Split Up

Admin - 0
Fans of the long-running television phenomenon Supernatural are in for a fresh dose of nostalgia and hunter drama with the upcoming release of the...

The Real Truth About Viral Kitchen Gadgets Before You Buy

Admin - 0
📢 As an Amazon Associate, I earn from qualifying purchases.If you had told me six months ago that a single purchase would change how...

Bird flu could devastate Macquarie Island. Why are we removing the scientists we need to understand it?

Admin - 0
Macquarie Island, a remote sub-Antarctic wildlife haven situated midway between Tasmania and Antarctica, is confronting an imminent ecological crisis. As the highly pathogenic H5N1...

Want to stay up to date with the latest news?

We would love to hear from you! Please fill in your details and we will stay in touch. It's that simple!