PROBLEM LINK:
Author: [Vivek Kumar Mishra(vkm41101 | CodeChef User Profile for Vivek Kumar Mishra | CodeChef)
Tester: Vivek Kumar Mishra
Editorialist: Harshit Pandey
DIFFICULTY:
SIMPLE
PREREQUISITES:
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 (xx)%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;
}