标签：Lucas定理

【SHOI 2015】超能粒子炮·改

题目描述有 $t$ 组数据，每组数据给定 $n,k$，求 $\sum_{i=0}^kC_n^i\mod 2333$ 的值。 $t\le 100000$，$n,k\le 10^{18}$。算法分析感觉可能是套路题…… 设 $f[n][k]=\sum_{i=0}^kC_n^i\mod 2333$......

Posted by WHZ0325 on 2019-05-01

【CTSC 2017】吉夫特

题目描述给定一个长度为 $n$ 的序列 $A$，求有多少个子序列满足所选下标集合为 ${b_1,b_2,\dots,b_k}$ 时 $a_{b_1}\ge a_{b_2}\ge\dots\ge a_{b_{k-1}}\ge a_{b_k}$ 且 $\prod_{i=2}^kC_{a_{i-1}......

Posted by WHZ0325 on 2019-04-28

【清华集训 2016】组合数问题

题目描述$t$ 组数据，每组数据给定 $n,m$ 和 $k$，求对于所有的 $0\le i\le n$，$0\le j\le \min(i,m)$ 有多少对 $(i,j)$ 满足 $C_i^j$ 是 $k$ 的倍数。 $1\le n,m\le 10^{18}$，$1\le t,k\le 100......

Posted by WHZ0325 on 2019-04-26

【SDOI 2010】古代猪文

题目描述给定两个整数 $n,g$，求 $g^{\sum_{k|n}C_n^k}\mod 999911659$ 的值。$1\le n,g\le 10^9$。算法分析当 $g$ 与模数 $999911659$ 互质时，根据欧拉定理得 $g^{\sum_{k|n}C_n^k}\mod 999911......

Posted by WHZ0325 on 2019-04-18