#P4591. [Shoi2015]超能粒子炮·改

    ID: 1765 传统题 1000ms 256MiB 尝试: 1472 已通过: 473 难度: 7 上传者: 标签>难度分类提高+/省选-组合数学Lucas 定理动态规划数位 DP上界限制状态前缀和优化 DPPascal 递推CF2200

[Shoi2015]超能粒子炮·改

[SHOI2015] 超能粒子炮·改

题目描述

曾经发明了脑洞治疗仪与超能粒子炮的发明家 SHTSC 又公开了他的新发明:超能粒子炮・改——一种可以发射威力更加强大的粒子流的神秘装置。

超能粒子炮・改相比超能粒子炮,在威力上有了本质的提升。它有两个参数 n,kn,k ,它会向每个编号为 00 到 kk (包含两端)的位置 ii 发射威力为 (ni) mod 2333\binom{n}{i}\bmod 2333 的粒子流。

约定 i>ni>n 时 (ni)=0\binom{n}{i}=0。现在给出参数 n,kn,k,求发射的粒子流的威力之和对 23332333 取模的结果。

输入格式

第一行一个整数 tt 表示数据组数。

之后 tt 行,每行两个整数 n,kn,k,含义如题面描述。

输出格式

tt 行,每行一个整数,表示其粒子流的威力之和模 23332333 的值。

3
5 5
10 7
1145 14
32
968
763

数据范围

0≤n,k≤10180\le n,k\le10^{18},1≤t≤1051\le t\le10^5。

数据比例 tt nn kk
10%10\% 1 ≤1000\le 1000
30%30\% ≤106\le 10^6
50%50\% ≤1018\le 10^{18} ≤1000\le 1000
70%70\% 100 ≤1018\le 10^{18}
100%100\% 10510^5