「BJOI 2019」堪破神机【数论】

题目大意

设用 1×21 \times 2 填满 2×n2 \times n 的方案数为 fnf_n,填满 3×n3 \times n 的方案数为 gng_n

给定 k,mk, m (m{2,3})(m \in \{ 2, 3 \}),求出 ansm\text{ans}_m998 244 353998\ 244\ 353 的值,其中:

ans2=1rl+1n=lr(fnk)ans3=1rl+1n=lr(gnk)\begin{aligned} \text{ans}_2 &= \frac{1}{r - l + 1} \sum_{n = l}^r \binom{f_n}{k} \\ \text{ans}_3 &= \frac{1}{r - l + 1} \sum_{n = l}^r \binom{g_n}{k} \end{aligned}

保证 1lr1018,1 \leqslant l \leqslant r \leqslant 10^{18}, 1k5011 \leqslant k \leqslant 501

查看更多