题意

\(n\)个人，每个人可以站红队，可以站蓝队，也可以当观察者。
红队获胜当且仅当站红队的人数大于站蓝队的人数。
问红队获胜的方案数，对小质数\(p\)取模。
\(n \leq {10} ^ {18}, p \leq {10} ^ {6}\)。

题解

列出式子：
\[ \sum_{i = 0} ^ n \binom{n}{i} \sum_{j = 0} ^ {\lfloor \frac{n - i - 1}{2} \rfloor} \binom{n - i}{j} \]
发现后面这个东西相当于
\[ \sum_{i = 0} ^ n \binom{n}{i} 2 ^ {n - i - 1} - \sum_{i = 0} ^ n \binom{n}{i} \binom{n - i}{i} \]
即将红队非输的方案数减去红队平的方案数得到的结果。
发现上面的东西等于
\[ \frac{1}{2} (3 ^ n - \sum_{i = 0} ^ n \binom{n}{i} \binom{n - i}{i}) \]
这东西怎么算