「Stoi2033」园游会

ID: 6976

远端评测题

1000ms

128MiB

难度: 4

上传者:

标签>

数学

O2优化

数位 dp

Lucas 定理

题目背景

我顶着大太阳只想为你撑伞
你靠在我肩膀深呼吸怕遗忘
因为捞鱼的蠢游戏我们开始交谈
多希望话题不断园游会永不打烊
气球在我手上我牵着你瞎逛
有话想对你讲你眼睛却装忙
鸡蛋糕跟你嘴角果酱我都想要尝
园游会影片在播放这个世界约好一起逛
——《园游会》

设 $F(x)=(x+1)\bmod 3-1$ ，给定 $n$ ，求：

\sum_{l=0}^n \sum_{r=l}^n F\left(C_{r}^{l}\right)

对 $1732073999$ 取模。其中 $C_{r}^{l}$ 为组合数，具体地，

C_{r}^{l}=\dfrac{r!}{l!(r-l)!}

本题有多组询问。

第一行两个正整数 $t,maxn$ ，表示询问组数与询问的最大可能值。

接下来 $t$ 行，每行一个正整数 $n$ 。

共 $t$ 行，第 $i$ 行一个整数，为第 $i$ 次询问的答案对 $1\ 732\ 073\ 999$ 取模的结果。

本题采用捆绑测试。

Subtask	分值	$1\le t \le$	$1\le n \le maxn \le$
$1$	$16$	$1$	$300$
$2$	$37$	$300$	$7 \times 10^6$
$3$	$47$	$3 \times 10^4$	$2 \times 10^{16}$

对于 $100\%$ 的数据，$1 \le t \le 3 \times 10^4,1 \le n \le maxn \le 2 \times 10^{16}$。