OMC074(C)

　各村人について素直であるかを表す真理値を素直度と呼び, $101$ を法とする原始根 $r$ について, $pe\overbrace{p...p}^{f(r^n)}er$ さんの素直度を $s(n)$ で表す. $1\leq n\leq 100$ の範囲外についても, $s(n) = s(n - 100)$ であることに留意する.
　条件より $pe\overbrace{p...p}^{f(r^{n})}er$, $pe\overbrace{p...p}^{f(r^{2n})}er$, ... , $pe\overbrace{p...p}^{f(r^{100n})}er$ のうちちょうど偶数人が素直であることから, $$\sum_{k = 1}^{100}s(kn) \equiv 0 \pmod{2}$$ が任意の $n$ で成立する. ここで, $a$ を $10$ と互いに素な整数とし, $n$ に $25a,5a,a$ をそれぞれ代入すると, $$\begin{aligned} 0 &\equiv \sum_{k = 1}^{100}s(25ak) \equiv s(25) + s(50) + s(75) + s(100) \pmod{2} \\ 0 &\equiv \sum_{k = 1}^{100}s(5ak) \equiv s(5) + s(10 ) + \cdots + s(100) \pmod{2} \\ 0 &\equiv \sum_{k = 1}^{100}s(ak) \equiv s(1) + s(2) + \cdots + s(100) \pmod{2} \end{aligned}$$ すなわち, $s(25),s(50),s(75),s(100)$ のうちちょうど偶数個が $1$ であり, $25$ の倍数でない $1$ 以上 $100$ 以下の $5$ の倍数 $k$ で $s(k) = 1$ なるものがちょうど偶数個あり, $5$ の倍数でない $1$ 以上 $100$ 以下の整数 $k$ で $s(k) = 1$ なるものがちょうど偶数個ある必要がある. 逆にこれらが十分条件であることもわかるから, $$m = \left(\sum_{k = 0}^{2}{_{4}}{\mathrm{C}}_{2k}\right)\left(\sum_{k = 0}^{8}{_{16}}{\mathrm{C}}_{2k}\right)\left(\sum_{k = 0}^{40}{_{80}}{\mathrm{C}}_{2k}\right) = 2^3\times 2^{15}\times 2^{79} = 2^{97}$$ より, 求める値は $\textbf{194}$ である.