A Dynamic Programming problem.
You’re trying to find the number of permutations of footmen/horsemen that match the given criterion. While you’re permuting, some problems are revisited. That’s when DP comes in handy:
- State S(n1, n2, k1, k2) – You’ve placed n1 footmen and n2 horsemen. The previous soldier is either a part of k1 consecutive footmen or k2 consecutive horsemen.
- Transition S(n1, n2, k1, k2) = S(n1 + 1, n2, k1 + 1, 0) + S(n1, n2 + 1, 0, k2 + 1) – You can either place a footman — which increases the number of consecutive footmen by one and resets the number of consecutive horsemen k2 — or a horseman.
Caution!
- Don’t forget the modulo 108.
C++ implementation but with values decreasing instead of increasing:
#include <iostream> #include <cstring> using namespace std; #define N 128 #define K 16 #define M 100000000 int nWays[N][N][K][K]; int N1, N2, K1, K2; long long getNWays(int n1, int n2, int k1, int k2) { if (n1 < 0 || n2 < 0 || k1 < 0 || k2 < 0) return 0; if(n1 == 0 && n2 == 0) return 1; if (nWays[n1][n2][k1][k2] != -1) return nWays[n1][n2][k1][k2]; return nWays[n1][n2][k1][k2] = (getNWays(n1 - 1, n2, k1 - 1, K2) + getNWays(n1, n2 - 1, K1, k2 - 1)) % M; } int main() { memset(nWays, -1, sizeof nWays); cin >> N1 >> N2 >> K1 >> K2; cout << getNWays(N1, N2, K1, K2) << endl; return 0; }