NPLQ19E Divide and Rule - Editorial

PROBLEM LINK : https://www.codechef.com/NPLQ2019/problems/NPLQ19E

Practice
Contest

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,2
r+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,2
r+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";
			
		}
		
	}

I have one doubt

For n = 0 , the answer is 0 1 right ? , because we can select 0 in one way , then why should we subtract 1 for odd numbers ?

Thanks

For N = 0, only subset you can form is of zero size which is even and we can’t have any odd sized subset.
But as it is clearly mentioned in problem, we can’t select a zero sized subset, so number of even sized subset is also zero.
Hence for anwser is 0 0 for N = 0.