BZOJ2142 礼物-扩展lucas

传送门

题意:

给定n及m个数a[1…m],再给定一个模数P,求$\sum_{i=1}^nC_{n-\sum_{j=1}^{i-1}a_j}^{a_i}$对P取模

($1≤n≤10_9,1≤m≤5$,设$ P=p_1^{c_1}\times p_2^{c_2}\times p_3^{c_3}\times …\times p_t^{c_t} $,$p_i$为质数,$1≤p_i^{c_i}≤10^5$)

阅读更多

Lucas定理的应用

出自17年10月某场洛谷比赛,开了个奇怪的脑洞。

题意:

有n盏灯环形排列,顺时针依次标号为1⋯n。初始时刻为0,初始时刻第i盏灯的亮灭a[i]给定,0表示灭,1表示亮。下一时刻每盏灯的亮灭取决于当前时刻这盏灯与顺时针方向下一盏灯的亮灭。若两盏灯状态相同,则下一时刻该灯灭,否则该灯亮。求时刻t第k盏灯的状态。
$n,t,k \leq 1e7$

阅读更多