A very interesting OA problem

Revision en1, by ShivanshJ, 2023-09-29 23:17:20

Many of my friends asked this interesting OA problem to me:

Given an array of strings $A$ of size $N$ and two integers $B$ and $C$.

Let $D$ be the number of strings of length $C$ that contains exactly $B$ of the strings in $A$ as substring.

Return $D$ mod $1e^9+9$.

Constraints $1 \le N \le 6$ $1 \le |A[i]| \le 50$ All the $N$ strings are distinct $0 \le B \le N$ $1 \le C \le 50.$

History

Revisions

Rev. Lang. By When Δ Comment
en8 ShivanshJ 2023-09-30 00:18:29 2 Tiny change: 'i-k+1][c][3]][i+2-inf' -> 'i-k+1][c][2]][i+2-inf'
en7 ShivanshJ 2023-09-30 00:10:03 13
en6 ShivanshJ 2023-09-30 00:08:07 13 (published)
en5 ShivanshJ 2023-09-30 00:06:38 2 Tiny change: 'if the $w^th$ string i' -> 'if the $w^{th}$ string i'
en4 ShivanshJ 2023-09-30 00:04:41 4
en3 ShivanshJ 2023-09-30 00:04:16 84 Tiny change: '$D$ mod $1e^9+9$.\n\n' -> '$D$ mod $10^9+9$.\n\n'
en2 ShivanshJ 2023-09-30 00:01:33 2370 Tiny change: 'e 50.$\n\n\n\n\n' -> 'e 50.$\n\nMy approach:\n\nLet \$dp[i][j][k][mask]\n\n\n\n\n'
en1 ShivanshJ 2023-09-29 23:17:20 439 Initial revision (saved to drafts)