Count sequences of positive integers having product X | C ++ program for the above approach ; Function to print the total number of possible sequences with product X ; Precomputation of binomial coefficients ; Max length of a subsequence ; Ways dp array ; Fill i slots using all the primes ; Subtract ways for all slots that exactly fill less than i slots ; Total possible sequences ; Print the resultant count ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int bin [ 3000 ] [ 3000 ] ; void countWays ( const vector < int > & arr ) { int mod = 1e9 + 7 ; bin [ 0 ] [ 0 ] = 1 ; for ( int i = 1 ; i < 3000 ; i ++ ) { bin [ i ] [ 0 ] = 1 ; for ( int j = 1 ; j <= i ; j ++ ) { bin [ i ] [ j ] = ( bin [ i - 1 ] [ j ] + bin [ i - 1 ] [ j - 1 ] ) % mod ; } } int n = 0 ; for ( auto x : arr ) n += x ; vector < int > ways ( n + 1 ) ; for ( int i = 1 ; i <= n ; i ++ ) { ways [ i ] = 1 ; for ( int j = 0 ; j < ( int ) arr . size ( ) ; j ++ ) { ways [ i ] = ( ways [ i ] * bin [ arr [ j ] + i - 1 ] [ i - 1 ] ) % mod ; } for ( int j = 1 ; j < i ; j ++ ) { ways [ i ] = ( ( ways [ i ] - bin [ i ] [ j ] * ways [ j ] ) % mod + mod ) % mod ; } } int ans = 0 ; for ( auto x : ways ) ans = ( ans + x ) % mod ; cout << ans << endl ; } int main ( ) { vector < int > arr = { 1 , 1 } ; countWays ( arr ) ; return 0 ; }