POTD_GFG_SOLUTIONS/SpecialDigits.cpp at main · Satwikdas122/POTD_GFG_SOLUTIONS · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//{ Driver Code Starts
#include<bits/stdc++.h>
using namespace std;


// } Driver Code Ends

#define ll long long
const int mod=1e9+7;
const int N=1e5+5;

bool f=0;
class Solution {
  public:

    ll binpow(ll a,ll b,ll p){

        if(b==0)
            return 1;

        ll t=binpow(a,b/2,p);

        if(b%2)
            return (((a*t)%p)*t)%p;
        else
            return ((t*t)%p);
    }

    ll fact[N],invfact[N];

    void init(){

        fact[0]=1;
        for(ll i=1;i<N;i++){
            fact[i]=i*fact[i-1]%mod;
        }

        invfact[N-1]=binpow(fact[N-1],mod-2,mod);

        for(ll i=N-2;i>=0;i--){
            invfact[i]=(i+1)*invfact[i+1]%mod;
        }

    }

    ll ncr(ll n,ll r,ll p){
        return (((fact[n]*invfact[n-r])%p)*invfact[r]%p)%p;
    }


    int bestNumbers(int n, int A, int B, int C, int D) {
        // code here
        if(!f){
            init();
            f=1;
        }

        long long ans=0;
        if(A==B){
            long long sum=(A*n)%mod;
             while(sum>0){
                if(sum%10==C || sum%10==D){
                    return 1;
                }
                sum/=10;
            }
            return 0;
        }

        for(int x=0;x<=n;x++){
            long long sum=x*A+(n-x)*B;
            bool flag=0;
            while(sum>0){
                if(sum%10==C || sum%10==D){
                    flag=1;
                    break;
                }
                sum/=10;
            }
            if(flag){
                ans+=ncr(n,x,mod);
                ans%=mod;
            }
        }

        return ans;
    }
};


//{ Driver Code Starts.

int main(){
    int t;
    scanf("%d ",&t);
    while(t--){

        int N;
        scanf("%d",&N);


        int A;
        scanf("%d",&A);


        int B;
        scanf("%d",&B);


        int C;
        scanf("%d",&C);


        int D;
        scanf("%d",&D);

        Solution obj;
        int res = obj.bestNumbers(N, A, B, C, D);

        cout<<res<<endl;

    }
}

// } Driver Code Ends