 # RSRV02-Editorial

Author: [Vivek Kumar Mishra(vkm41101 | CodeChef User Profile for Vivek Kumar Mishra | CodeChef)
Tester: Vivek Kumar Mishra
Editorialist: Harshit Pandey

SIMPLE

# PREREQUISITES:

Discrete Structures

# PROBLEM:

Find the No. of sets of ordered pairs such that if {a,b} belongs to the set, then either a=b, or {b,a} does not belong to the set.

# QUICK EXPLANATION:

The answer will Be the Number of Antisymmetric Relations Possible.

# EXPLANATION:

If we clearly observe, we have two different cases, Either a=b, or a!=b.
In the first case, we have {a,a}, for which there are two responsibilities, Either we take it, or we don’t. No of such possibilities would be 2^{n} where n is the number of elements.
For the second case, we have thre possibilities, as listed below.

• {a,b} and {b,a} do not belong to the set
• {a,b} is absent from the set, and {b,a} is present.
• {a,b} is present in the set, and {b,a} is absent.
Now the Number of such ordered sets {a,b} that need to be considered= \frac{{N}^{2}-{N}}{2}

Therefore the Total Possibilities for choosing such pairs is 2^{N}* 3^{\frac{{N}^{2}-{N}}{2}}

# SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>

using namespace std;

#define nln ‘\n’
#define fr(i, l, h, s) for (long long i = l; i < h; i += s)
#define ll long long
const ll M = 1e9+7;

/===================================================================/

ll intfromstring(string s)
{
int n=s.length();
ll num=0;
fr(i,0,n,1) num=num*10+(s[i]-‘0’);
return num;
}

ll factn(ll n)
{
ll prod=1;
if(n==0) return 1;
fr(i,1,n+1,1)prod*=i;
return prod;
}

ll factlogn(ll lo, ll hi)
{
if(hi-lo==1) return hilo;
if(hi-lo==2) return hi
(hi-1)*(lo);
int mid=(hi+lo)/2;
return factlogn(lo,mid) * factlogn(mid+1,hi);
}

ll binarySearch(ll arr[], ll lo, ll hi, ll x)
{
if(hi-lo>1)
{
ll mid=(lo+hi)/2;
if(arr[mid]==x) return mid;
if(arr[mid] > x) return binarySearch(arr, lo, mid-1, x);
if(arr[mid] < x) return binarySearch(arr, mid+1, hi, x);
}
return -1;
}

ll firstOccurence(ll arr[], ll lo, ll hi, ll x)
{
if (hi - lo > 1)
{
ll mid = (lo + hi) / 2;
if (arr[mid] == x)
return firstOccurence(arr, lo, mid, x);
if (arr[mid] < x)
return firstOccurence(arr, mid + 1, hi, x);
if (arr[mid] > x)
return firstOccurence(arr, lo, mid - 1, x);
}
if (arr[lo] == x)
return lo;
if (arr[hi] == x)
return hi;
return -1;
}

ll lastOccurence(ll arr[], ll lo, ll hi, ll x)
{
if (hi - lo > 1)
{
ll mid = (lo + hi) / 2;
if (arr[mid] == x)
return lastOccurence(arr, mid, hi, x);
if (arr[mid] < x)
return lastOccurence(arr, mid + 1, hi, x);
if (arr[mid] > x)
return lastOccurence(arr, lo, mid - 1, x);
}
if (arr[hi] == x)
return hi;
if (arr[lo] == x)
return lo;
return -1;
}

ll count(ll arr[], ll n, ll x)
{
return lastOccurence(arr, 0, n - 1, x) - firstOccurence(arr, 0, n - 1, x) + 1;
}

long long int maxl(long long int a, long long int b)
{
if (a > b)
return a;
return b;
}

long long int minl(long long int a, long long int b)
{
if (a < b) return a;
return b;
}

long long int absl(long long int a)
{
if(a<0)return -a;
return a;
}

ll powb(int base, int po)
{
base%=M;
if(base==1 || po==0) return 1;
if(po==1) return base%M;
if (po&1)
{
ll x=powb(base, po/2)%M;
return (((x*x)%M)base)%M;
}
ll x = powb(base, po / 2)%M;
return (x
x)%M;
}

/====================================================================/

void testCase()
{
ll n;
cin >> n;
ll pow2=n, pow3=(n*(n-1))/2;
ll tw=powb(2,pow2)%M;
ll thr=powb(3,pow3)%M;
ll ans=tw*thr%M;
ll arr[n];
for(ll& x:arr) cin >> x;
cout << ans << nln;
return;
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“outputTestData.in”, “r”, stdin);
freopen(“outputTestAns.out”, “w”, stdout);
#endif
int t = 1;
cin >> t;
while (t–)
{
testCase();
}
return 0;
}