Count of sub | C ++ implementation of the approach ; Function to return the total number of required sub - sets ; Variable to store total elements which on dividing by 3 give remainder 0 , 1 and 2 respectively ; Create a dp table ; Process for n states and store the sum ( mod 3 ) for 0 , 1 and 2 ; Use of MOD for large numbers ; Final answer store at dp [ n - 1 ] [ 0 ] ; Driver Program
#include <bits/stdc++.h> NEW_LINE #define MOD  1000000007 NEW_LINE #define ll  long long int NEW_LINE using namespace std ; int totalSubSets ( ll n , ll l , ll r ) { ll zero = floor ( ( double ) r / 3 ) - ceil ( ( double ) l / 3 ) + 1 ; ll one = floor ( ( double ) ( r - 1 ) / 3 ) - ceil ( ( double ) ( l - 1 ) / 3 ) + 1 ; ll two = floor ( ( double ) ( r - 2 ) / 3 ) - ceil ( ( double ) ( l - 2 ) / 3 ) + 1 ; ll dp [ n ] [ 3 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; dp [ 0 ] [ 0 ] = zero ; dp [ 0 ] [ 1 ] = one ; dp [ 0 ] [ 2 ] = two ; for ( ll i = 1 ; i < n ; ++ i ) { dp [ i ] [ 0 ] = ( ( dp [ i - 1 ] [ 0 ] * zero ) + ( dp [ i - 1 ] [ 1 ] * two ) + ( dp [ i - 1 ] [ 2 ] * one ) ) % MOD ; dp [ i ] [ 1 ] = ( ( dp [ i - 1 ] [ 0 ] * one ) + ( dp [ i - 1 ] [ 1 ] * zero ) + ( dp [ i - 1 ] [ 2 ] * two ) ) % MOD ; dp [ i ] [ 2 ] = ( ( dp [ i - 1 ] [ 0 ] * two ) + ( dp [ i - 1 ] [ 1 ] * one ) + ( dp [ i - 1 ] [ 2 ] * zero ) ) % MOD ; } return dp [ n - 1 ] [ 0 ] ; } int main ( ) { ll n = 5 ; ll l = 10 ; ll r = 100 ; cout << totalSubSets ( n , l , r ) ; return 0 ; }