PROBLEM LINK : CodeChef: Practical coding for everyone
Author: Shivang Awasthi
Tester: Shivang Awasthi
Editorialist: Shivang Awasthi
DIFFICULTY:
Simple
PREREQUISITES:
Math, Combinatorics
PROBLEM:
Find the number of ways to divide a set of size N into even and odd sized non empty subsets.
QUICK EXPLANATION:
The answer is there are pow(2,N-1)-1 and pow(2,N-1) even and odd sized non empty subsets
EXPLANATION:
Considering (N,r) for r < 0 and r > N is 0,
the number of even sized subsets is sum of (N,2r) for r running from 0 to N/2, and the
number of odd sized subsets is sum of (N,2r+1) for r running from 0 to N/2.
The sum of (N,2r) for r running from 0 to N/2 is pow(2,N-1).
The sum of (N,2r+1) for r running from 0 to N/2 is also pow(2,N-1).
These are the popular results from combinatorics and can be verified from here and here.
As we don’t need empty subset,
the answer for even sized subsets is pow(2,N-1)-1.
the answer for odd sized subsets is pow(2,N-1)-1.
The answer for N = 0 is 0 for both even and odd sized subsets .
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll N = 3000;
const ll MOD = (ll)1e9+7;
const ll inf = (ll)1e18+6;
// const ll M = (ll)2000;
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
ll add(ll x, ll y) {
x += y;
if (x >= MOD) return x - MOD;
return x;
}
ll sub(ll x, ll y) {
x -= y;
if (x < 0) return x + MOD;
return x;
}
ll mult(ll x, ll y) {
return (x * y) % MOD;
}
ll bin_pow(ll x, ll p) {
if (p == 0) return 1;
if (p & 1) return mult(x, bin_pow(x, p - 1));
return bin_pow(mult(x, x), p / 2);
}
ll rev(ll x) {
return bin_pow(x, MOD - 2);
}
bool cmp(pll A, pll B)
{
return A.fi * B.se + A.se < B.fi * A.se + B.se;
}
int main()
{
ios::sync_with_stdio(true);
cin.tie(nullptr);
cout.precision(20);
cout << fixed;
#ifdef LOCAL_DEFINE
freopen("input.txt", "rt", stdin);
#endif
ll t;
cin >> t;
while(t--)
{
ll n;
cin >> n;
if(n == 0)
cout << 0 << " " << 0 << "\n";
else
cout << (bin_pow(2, n - 1) - 1 + MOD) % MOD << " " << bin_pow(2, n - 1) << "\n";
}
}