Leia o enunciado antes de continuarmos.
Este problema é descrito em [Halim] e tem uma resolução de programação dinâmica.
A ideia central é que podemos deconstruir o problema original de contar quantas somas existem com K parcelas com total N, estabelecendo uma relação do problema original com subproblemas mais simples.É esta relação que nos permitirá desenvolver uma solução de programação dinâmica!
Vamos designar o número de soluções distintas por sum(N,K).
Por exemplo, se uma das parcelas fosse o número 5, o resto da solução seria dado por sum(N-5, K-1). Isto porque já descontámos 5 valores ao total N, e gastámos uma parcela no número 5. Se a parcela seguinte fosse um 3, o resto da solução seria sum(N-8, K-2)...
Isto indica que sum(N,K) pode ser dado por N+1 subproblemas, cada um correspondendo a tirar uma parcela com um número de 0 a N:
sum(N,K) = sum(N-0,K-1) + sum(N-1,K-1) + sum(N-2,K-1) + ... + sum(N-N,K-1)
Para evitar repetições no cálculo de soluções, vamos guardar numa matriz as soluções sols(N,K) que formos calculando. Para isso criamos a matriz sols como atributo estático da nossa classe:
static final int UNKNOWN = 0;
static long[][] sols = new long[101][101]; // N,K <= 100, we'll not use indexes 0
A seguinte função calcula um valor de sum(N,K) a partir dos seus subproblemas, usando memorização para ir armazenando soluções:
static void computeAdds(int N, int K) {
if (sols[N][K] != UNKNOWN) // already computed: carry on, there's nothing to do...
return;
if (K==1)
sols[N][K] = 1; // if there is just one parcel, the only possible solution is N itself
else {
long sum = 0;
for(int i=0; i<=N; i++) {
computeAdds(N-i, K-1);
sum += sols[N-i][K-1];
sum %= 1000000; // keep it small
}
sols[N][K] = sum; // keep solution for future use
}
}
Um detalhe sobre o uso do módulo 1000000. O enunciado pede o output neste formato porque os números tornar-se-iam absolutamente gigantescos para N e K grandes. Desta forma, temos a garantia que as soluções dão números relativamente pequenos.
Este truque é possível porque na aritmética módulo m podemos aplicar o módulo a cada uma das parcelas da soma:
(a + b) mod m == ((a mod m) + b) mod m
Nós temos algum hábito deste tipo de aritmética devido à forma como os relógios usam aritmética módulo 12. Eg, se forem agora 11 horas, três horas depois serão duas horas porque (11+3) mod 12 = 2.
A disciplina de Matemática Discreta explora este tópico (os vídeos estão disponíveis no youtube).
Com esta função resta-nos apenas ler cada par de valores N,K e ir calculando as soluções. De notar que à medida que os pares vão sendo calculados, a matriz sols vai sendo preenchida, e os pares seguintes tenderão a ser calculados mais rapidamente:
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
int N = sc.nextInt(), // 1 <= N <= 100
K = sc.nextInt(); // 1 <= K <= 100
if (N==0 && K==0) // pair 0 0 marks EOF
break;
computeAdds(N,K);
System.out.println(sols[N][K]);
}
sc.close();
}
Referência: Steven Halim - Competitive Programming 3