Number of ways to choose K intersecting line segments on X | C ++ program to find Number of ways to choose K intersecting line segments on X - axis ; Function to find ( a ^ b ) % mod in log b ; Till power becomes 0 ; If power is odd ; Multiply base ; Divide power by 1 ; Function to find nCk ; Base case ; Apply formula to find nCk ; Function to find the number of ways ; sort the given lines ; Find the number of total case ; Declare a multiset ; loop till N ; Check if smallest element is smaller than lines [ i ] ; Erase first element ; Exclude the odd cases ; Modulus operation ; Insert into multiset ; Function to precompute factorial and inverse ; Pre - compute factorial and inverse ; Driver code ; Function to pre - compute factorial and inverse
#include <bits/stdc++.h> NEW_LINE using namespace std ; const long long mod = 1000000007 ; const int MAXN = 1001 ; long long factorial [ MAXN ] , inverse [ MAXN ] ; long long power ( long long a , long long b ) { long long res = 1 ; while ( b > 0 ) { if ( b % 2 == 1 ) { res = ( res * a ) % mod ; } a = ( a * a ) % mod ; b >>= 1 ; } return res ; } long long nCk ( int n , int k ) { if ( k < 0 k > n ) { return 0 ; } long long ans = factorial [ n ] ; ans = ( ans * inverse [ n - k ] ) % mod ; ans = ( ans * inverse [ k ] ) % mod ; return ans ; } void numberOfWays ( vector < pair < int , int > > lines , int K , int N ) { sort ( lines . begin ( ) , lines . end ( ) ) ; long long total_case = nCk ( N , K ) ; multiset < int > m ; for ( int i = 0 ; i < N ; i ++ ) { while ( ! m . empty ( ) && ( * m . begin ( ) < lines [ i ] . first ) ) { m . erase ( m . begin ( ) ) ; } total_case -= nCk ( m . size ( ) , K - 1 ) ; total_case += mod ; total_case %= mod ; m . insert ( lines [ i ] . second ) ; } cout << total_case << endl ; } void preCompute ( ) { long long fact = 1 ; factorial [ 0 ] = 1 ; inverse [ 0 ] = 1 ; for ( int i = 1 ; i < MAXN ; i ++ ) { fact = ( fact * i ) % mod ; factorial [ i ] = fact ; inverse [ i ] = power ( factorial [ i ] , mod - 2 ) ; } } int main ( ) { int N = 3 , K = 2 ; vector < pair < int , int > > lines ; preCompute ( ) ; lines . push_back ( { 1 , 3 } ) ; lines . push_back ( { 4 , 5 } ) ; lines . push_back ( { 5 , 7 } ) ; numberOfWays ( lines , K , N ) ; return 0 ; }