Cod sursa(job #2587437)

Utilizator alexradu04Radu Alexandru alexradu04 Data 22 martie 2020 17:57:12
Problema Ratphu Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>
#include <algorithm>
long long dp[(1<<18)][25];
int digits[20];
FILE *in = fopen("ratphu.in","r");
FILE *out = fopen("ratphu.out","w");
signed main() {
    long long n;
    int p,numberOfDigits=0;
    fscanf(in,"%lld %d",&n,&p);
    while(n) {
        digits[++numberOfDigits]=n%10;
        n/=10;
    }
    std::reverse(digits + 1,digits+numberOfDigits + 1);
    dp[0][0]=1;
    for(int i=0;i< (1<<18) ;++i) {
        for(int j=0;j<p;++j) {
            if(dp[i][j])
                for(int k=1;k<=numberOfDigits;++k) {
                    if((i&(1<<(k-1))) == 0) {
                        dp[i | (1<<(k-1))][(j*10+digits[k])%p]+=dp[i][j];
                    }
                }
        }
    }
    fprintf(out,"%lld",dp[(1<<numberOfDigits)-1][0]);
    return 0;
}