Problem 949
Left vs Right II
Left and Right play a game with a number of words, each consisting of L’s and R’s, alternating turns. On Left’s turn, for each word, Left can remove any number of letters (possibly zero), but not all the letters, from the left side of the word. However, at least one letter must be removed from at least one word. Right does the same on Right’s turn except that Right removes letters from the right side of each word. The game continues until each word is reduced to a single letter. If there are more L’s than R’s remaining then Left wins; otherwise if there are more R’s than L’s then Right wins. In this problem we only consider games with an odd number of words, thus making ties impossible.
Let $G(n, k)$ be the number of ways of choosing $k$ words of length $n$, for which Right has a winning strategy when Left plays first. Different orderings of the same set of words are to be counted separately.
It can be seen that $G(2, 3)=14$ due to the following solutions (and their reorderings):
$$\begin{aligned}
(\texttt{LL},\texttt{RR},\texttt{RR})&:3\text{ orderings}\\
(\texttt{LR},\texttt{LR},\texttt{LR})&:1\text{ ordering}\\
(\texttt{LR},\texttt{LR},\texttt{RR})&:3\text{ orderings}\\
(\texttt{LR},\texttt{RR},\texttt{RR})&:3\text{ orderings}\\
(\texttt{RL},\texttt{RR},\texttt{RR})&:3\text{ orderings}\\
(\texttt{RR},\texttt{RR},\texttt{RR})&:1\text{ ordering}
\end{aligned}
$$You are also given $G(4, 3)=496$ and $G(8, 5)=26359197010$.
Find $G(20, 7)$ giving your answer modulo $1001001011$.
小左对小右（二）
小左和小右在用若干个由字母L和R组成的单词玩游戏，两人轮流行动。在小左的回合中，小左可以从每个单词的左侧移除任意个字母（可以为零），但不能移除所有字母，且必须从至少一个单词中移除一个字母；小右则类似地从单词的右侧移除字母。游戏持续进行，直到每个单词都只剩下一个字母：如果剩余的字母L比字母R更多，则小左获胜；反之如果剩余的字母R比字母L多，则小右获胜。本题假设单词数目总是奇数个，因此不可能出现平局。
记$G(n, k)$为游戏开始时有$k$个长度为$n$的单词且当小左先行动时小右有必胜策略的局面数；由相同单词的不同排列构成的局面分别计数。
已知$G(2, 3)=14$，包括如下的几种局面（包括其不同排列）：
$$\begin{aligned}
(\texttt{LL},\texttt{RR},\texttt{RR})&:3\text{种排列}\\
(\texttt{LR},\texttt{LR},\texttt{LR})&:1\text{种排列}\\
(\texttt{LR},\texttt{LR},\texttt{RR})&:3\text{种排列}\\
(\texttt{LR},\texttt{RR},\texttt{RR})&:3\text{种排列}\\
(\texttt{RL},\texttt{RR},\texttt{RR})&:3\text{种排列}\\
(\texttt{RR},\texttt{RR},\texttt{RR})&:1\text{种排列}
\end{aligned}$$
此外还已知$G(4, 3)=496$，$G(8, 5)=26359197010$。
求$G(20, 7)$，并对$1001001011$取余作为你的答案。