Участник:Rimon/Ada and Digits

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/submit/ADADIG/

C++(gcc 8.3)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
 
using namespace std;
 
const int MAX = 300005;
const int modulo = 1000000007;
 
int T, N;
int result;
int fac[MAX];
 
int binaryPower (int a, int b, int modulo) {
    if (b == 0) {
        return 1 % modulo;
    }
    if (b & 1) {
        return 1LL * binaryPower(a, b - 1, modulo) * a % modulo;
    }
    int half = binaryPower(a, b >> 1, modulo);
    return 1LL * half * half % modulo;
}
int inverse (int a, int modulo) {
    return binaryPower(a, modulo - 2, modulo);
}
void go (int digit, int product, int sum, int takenDigits, int denominator) {
    if (sum > N) {
        return;
    }
    if (product == 1) {
        int ones = N - sum;
        int numerator = fac[takenDigits + ones];
        denominator = 1LL * denominator * fac[ones] % modulo;
        result = (result + 1LL * numerator * inverse(denominator, modulo) % modulo) % modulo;
        return;
    }
    if (digit > 9) {
        return;
    }
    go(digit + 1, product, sum, takenDigits, denominator);
    int count = 0;
    while (product % digit == 0) {
        count ++;
        product /= digit;
        go(digit + 1, product, sum + digit * count, takenDigits + count, 1LL * denominator * fac[count] % modulo);
    }
}
 
 
int main(int argc, const char * argv[]) {
    fac[0] = 1;
    for (int i = 1; i < MAX; i ++) {
        fac[i] = 1LL * fac[i - 1] * i % modulo;
    }
 
    scanf("%d", &T);
    while (T --) {
        scanf("%d", &N);
        result = 0;
        go(2, N, 0, 0, 1);
        printf("%d\n", result);
    }
 
    return 0;
}