Mini-project Part 5: Arrangement Counter

The closing project. One program answers four types of combinatorics questions, all modulo 1,000,000,007 — combining the counting rules (Chapter 16), permutations and combinations (Chapter 17), and modular power and inverse (Chapter 14).

The problem

The OSN committee. The committee wants one arrangement-counting program. There are q questions, each starting with a type number:

Type Extra input What is computed
1 n r P(n, r) — choosing r from n with order
2 n r C(n, r) — choosing r from n without order
3 s the number of distinct letter arrangements of the word s
4 b k the number of paths on a b × k board (right/down)

All answers are printed modulo 1,000,000,007.

Constraints. q ≤ 100,000. For types 1, 2, and 4: the values go up to 1,000,000. For type 3: s contains only uppercase letters A–Z, and the total length of all words in one input file is at most 1,000,000. If r > n, the answer is 0.

Sample input:

5
1 10 3
2 10 3
3 OSNOSN
4 3 4
2 1000000 500000

Sample output:

720
120
90
10
996692777

What to build

  1. Prepare a factorial table up to 1,000,000 once at the start.
  2. Write pangkat_mod ("modular power") and invers ("inverse") (Chapter 14).
  3. Write permutasi(n, r) ("permutation") = n! × ((n−r)!)⁻¹.
  4. Write kombinasi(n, r) ("combination") = n! × (r!)⁻¹ × ((n−r)!)⁻¹.
  5. For type 3: count the occurrences of each letter, then compute length! × (count₁!)⁻¹ × (count₂!)⁻¹ × …
  6. For type 4: C((b−1) + (k−1), b−1).

Then add a tester: for n ≤ 8 and words of length ≤ 7, compare the formula's answer with direct enumeration (next_permutation for type 3, masks for type 2). This tester does not print to cout — use cerr so it does not interfere with judging.

Counting the time

Part Cost
preparing factorials 10⁶ steps, once
one question of type 1, 2, 4 O(log p) ≈ 30 steps
one question of type 3 O(word length + 26 log p)

For q = 100,000, the total is a few million steps — well within the time limit.

One call to the inverse costs 30 steps, and type 2 needs two. If the problem were tighter, a table of inverse factorials could also be prepared at the start so that every question becomes O(1). Try it once you are done.

Hints

  • All multiplications use long long and % MOD at every step.
  • 'A' through 'Z' are counted with an array of size 26: the index is s[i] - 'A'.
  • The factorial of 0 is 1 — do not let the table start from 1.
  • For types 1 and 2, check r > n first and print 0.

Files

Compile and run:

g++ -std=c++17 -O2 -o susunan projects/05-penghitung-susunan/starter.cpp
./susunan < projects/05-penghitung-susunan/contoh-masukan.txt

Done?

If all four types are correct, the tester finds no differences, and you can explain why the division in the combination formula must be replaced by multiplication by the inverse — this project is finished, and so is the book.

The next step is not a new chapter, but practice: open the OSN problem archive on the online judge you registered on in Chapter 01, start from the regency-level problems, and work on them in the same order as in this book — read the constraints, count the number of steps, plan on paper, write a brute force, test, and only then speed it up.