Count ways to make the number formed by K concatenations of a numeric string divisible by 5 | C ++ program for the above approach ; Function to find the value of a ^ b modulo 1000000007 ; Stores the resultant value a ^ b ; Find the value of a ^ b ; Function to count the number of ways such that the formed number is divisible by 5 by removing digits ; Stores the count of ways ; Find the count for string S ; If the digit is 5 or 0 ; Find the count of string for K concatenation of string S ; Find the total count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; typedef long long LL ; const int MOD = 1000000007 ; int exp_mod ( LL a , LL b ) { LL ret = 1 ; for ( ; b ; b >>= 1 , a = a * a % MOD ) { if ( b & 1 ) ret = ret * a % MOD ; } return ret ; } int countOfWays ( string s , int k ) { int N = s . size ( ) ; LL ans = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( s [ i ] == '5' s [ i ] == '0' ) { ans = ( ans + exp_mod ( 2 , i ) ) % MOD ; } } LL q = exp_mod ( 2 , N ) ; LL qk = exp_mod ( q , k ) ; LL inv = exp_mod ( q - 1 , MOD - 2 ) ; ans = ans * ( qk - 1 ) % MOD ; ans = ans * inv % MOD ; return ans ; } int main ( ) { string S = "1256" ; int K = 1 ; cout << countOfWays ( S , K ) ; return 0 ; }