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.$$$

Tags dp, interesting problem, bitmask, cool problems

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English 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 English ShivanshJ 2023-09-30 00:10:03 13
en6 English ShivanshJ 2023-09-30 00:08:07 13 (published)
en5 English ShivanshJ 2023-09-30 00:06:38 2 Tiny change: 'if the $w^th$ string i' -> 'if the $w^{th}$ string i'
en4 English ShivanshJ 2023-09-30 00:04:41 4
en3 English 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 English 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 English ShivanshJ 2023-09-29 23:17:20 439 Initial revision (saved to drafts)