PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kingmessi
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
PROBLEM:
Count the number of arrays D of length N such that:
- D_1 + D_2 + \ldots + D_N = 2N
- There exists a simple connected bipartite graph G on N vertices that has D as its degree sequence.
EXPLANATION:
The sum of degrees of all vertices in a graph is exactly twice the number of edges - after all, each edge increases the degree of exactly two vertices.
Since we want D to be the degree sequence of a graph, and D is to have a sum of 2N, the graph G weâre considering should have exactly N edges.
The only simple and connected graphs with N vertices and N edges, are those obtained by taking a tree and adding a single edge to it.
An alternate way of looking at such a graph, is a single cycle with trees hanging off of each of its vertices.
We also want the graph to be bipartite, so the single cycle that exists should be of even size (and also have \geq 4 vertices, otherwise it wouldnât be simple).
Now, note that we want to count degree sequences, and not graphs.
This distinction is important, because multiple graphs can have the same degree sequence.
So, letâs fix an array D whose elements are \geq 1 and sum is 2N, and see when we can create a valid graph.
First, note that any vertices that lie on a cycle must have a degree thatâs \geq 2.
So, since we want a cycle thatâs of size \geq 4, we definitely want at least 4 vertices whose degree is \geq 2.
Let k denote the number of vertices with degree 2, and suppose k\geq 4.
As it turns out, this condition is nearly sufficient for a graph to exist!
Specifically,
- If k is even, a valid graph always exists.
- If k is odd, a valid graph doesnât exist if and only if k = N.
Proof
When k is even, we have a relatively simple construction: take all k vertices and arrange them into a large cycle; then simply attach the degree 1 vertices as leaves to cycle vertices to fulfill the degrees.
This works because there are N-k vertices with degree 1, and the cycle vertices need a total of 2N - (N-k) - 2k = N-k âextraâ degrees, since each of them already receives 2 from being on the cycle.
Next, letâs look at odd k.
If k = N, weâre forced to have D_i = 2 for every i, and the only choice is to put all k vertices in a single cycle of length N.
This cycle isnât bipartite, since itâs odd.
That leaves us with k \lt N.
Here, since the sum is 2N, there must exist some x such that D_x \geq 3.
Apart from this x, choose any other vertex y such that D_y \geq 2.
Now, form a cycle with all the degree \geq 2 vertices other than y.
Then, attach y to x, and some degree 1 vertex to y.
After this, just as in the first case we can simply attach degree 1 vertices as leaves to anything that needs it.
So, we take almost any array D with a sum of 2N: only a small handful of them are âbadâ.
The total number of arrays of positive integers whose length is N and sum is 2N is \binom{2N-1}{N-1}, calculated using stars and bars.
From this, we subtract âbadâ arrays, which are the ones with k \leq 3 elements that are \geq 2.
For a fixed k,
- Fix which elements are \geq 2 in \binom{N}{k} ways.
- All the other (N-k) elements are 1, so the sum of these k elements should be exactly 2N - (N-k) = N+k.
- The number of ways to have k elements that are \geq 2 sum to N+k is \binom{N-1}{k-1}, again as a result of stars-and-bars (to bring it to the necessary form, subtract 1 from each of the k elements, and also subtract k from the target sum).
When N is odd (and \gt 3), we also subtract a further 1: since k = N isnât allowed there, and thereâs exactly one array with that.
So, the final answer is
This can be computed in constant time with precomputed factorials and inverse factorials.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Author's code (C++)
//Har Har Mahadev
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
#define NCR
#define PRIME M
int pw(int a,int p=M-2,int MOD=M){
int result = 1;
while (p > 0) {
if (p & 1)
result = a * result % MOD;
a = a * a %MOD;
p >>= 1;
}
return result;
}
int fact[2000005],invfact[2000005];
void init(){
int p=PRIME;
fact[0]=1;
int i;
for(i=1;i<2000005;i++){
fact[i]=(i*fact[i-1])%p;
}
i--;
invfact[i]=pw(fact[i],p-2,p);
for(i--;i>=0;i--){
invfact[i]=(invfact[i+1]*(i+1))%p;
}
}
int ncr(int n,int r){
if(r>n || r<0)return 0;
int res = (((fact[n]*invfact[r])%PRIME)*invfact[n-r])%PRIME;
res = res+PRIME;res %= PRIME;
return res;
}
void solve()
{
int n;
cin >> n;
int ans = ncr(2*n-1,n-1);
ans -= ((ncr(n,3)*ncr(n-1,2))%M);ans %= M;
ans -= ((ncr(n,2)*(n-1))%M);ans %= M;
ans -= n;ans%=M;
if(n > 3 && (n&1))ans--;
ans += M;ans %= M;
cout << ans << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
int t;
cin >> t;
while(t--)
solve();
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e6+1;
ll factorialNumInverse[N + 1];
ll naturalNumInverse[N + 1];
ll factorial[N + 1];
ll Binomial(ll N, ll R, ll p)
{
ll ans = ((factorial[N] * factorialNumInverse[R])
% p * factorialNumInverse[N - R])
% p;
return ans;
}
void InverseofNumber(ll p)
{
naturalNumInverse[0] = naturalNumInverse[1] = 1;
for (int i = 2; i <= N; i++)
naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;
}
void InverseofFactorial(ll p)
{
factorialNumInverse[0] = factorialNumInverse[1] = 1;
for (int i = 2; i <= N; i++)
factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
}
void FACTORIAL(ll p)
{
factorial[0] = 1;
for (int i = 1; i <= N; i++) {
factorial[i] = (factorial[i - 1] * i) % p;
}
}
void start()
{
ll p = 1000000007;
InverseofNumber(p);
InverseofFactorial(p);
FACTORIAL(p);
}
int main() {
ll tt=1;
cin>>tt;
start();
while(tt--){
ll n;
cin>>n;
if(n<=3){
cout<<"0\n";
continue;
}
ll total=Binomial(2*n-1,n,1000000007);
for(int i=1;i<=3;i++){
ll cnt=(Binomial(n-1,n-i,1000000007)*Binomial(n,i,1000000007))%1000000007;
total+=(1000000007-cnt);
total%=1000000007;
}
if(n%2){
total+=(1000000006);
total%=1000000007;
}
cout<<total<<"\n";
}
}
Editorialist's code (Python)
mod = 10**9 + 7
maxn = 2 * 10**6
fac = [1] * maxn
for i in range(1, maxn): fac[i] = fac[i-1] * i % mod
inv = fac[:]
inv[-1] = pow(fac[-1], mod-2, mod)
for i in reversed(range(maxn-1)): inv[i] = inv[i+1] * (i+1) % mod
def C(n, r):
if n < r or r < 0: return 0
return fac[n] * inv[r] % mod * inv[n-r] % mod
for _ in range(int(input())):
n = int(input())
n -= 1
ans = C(2*n, n) + C(2*n, n-1)
n += 1
for k in range(n-3, n+1):
ans -= C(n, k) * C(n-1, k)
if n%2 == 1 and n > 3: ans -= 1
print(ans%mod)