[SHOI2015]超能粒子炮·改

link

推柿子。

\[f(n,k) \]

\[=\sum\limits_{i=1}^kC_n^i\%P \]

\[=\sum\limits_{i=1}^kC_{n/P}^{i/P}\times C_{n\%P}^{i\%P}\%P \]

\[=\sum\limits_{k=0}^{\lfloor\frac{k}{P}\rfloor-1}C_{\lfloor\frac{n}{P}\rfloor}^k\times\sum\limits_{j=0}^{P-1}C_{n\%P}^j+C_{\lfloor\frac{n}{P}\rfloor}^{\lfloor\frac{k}{P}\rfloor}\sum\limits_{j=0}^{k\%P}C_{n\%P}^j \]

\[=f(n/P,k/P-1)\times f(n\%P,P-1)+C_{n/P}^{k/P}f(n\%P,k\%P) \]

然后就可以递归处理了。边界特判比较特殊，当两个参数有一个小于0时要返回0，而且lucas函数里一定要取模（调了半天），再有就是当m小于n时f(m,n)是有值的。

code:

#include
//#define zczc
#define int long long
const int N=3010;
const int mod=2333;
using namespace std;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}

int c[N][N],s[N][N];
inline int lucas(int s1,int s2){
	if(s1