[ural 2126]. Partition into Teams

题意

\(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}) \]
这东西怎么算

上一篇:Office365 - Form无法访问的解决方案


下一篇:Office 365:Microsoft Teams 用于协作相关的工具和服务