2019沈阳网络赛 E(贝尔数)

$Description$
图片说明

$Solution$
答案就是贝尔数 $B_n$
$B_0=B_1=1,B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}\cdot B_k$
$p \; is \; prime ,B_{n+p}\equiv B_n+B_{n+1} \; mod \; (p)$
$B_{n+p^m}\equiv m\cdot B_n+B_{n+1} \; mod \; (p)$
$k=\frac{n}{p},B_{n}=\sum_{i=0}^{k}\binom{k}{i}\cdot B_{n\%p+i}$

$Code$

#include<bits/stdc++.h>
#define me(a,Y) memset(a,Y,sizeof(a))
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
#define sc scanf
#define itn int
#define STR clock_t startTime = clock();
#define END clock_t endTime = clock();cout << double(endTime - startTime) / CLOCKS_PER_SEC *1000<< "ms" << endl;
using namespace std;
const int N=1e6+5;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
inline ll mul_64(ll Y,ll y,ll c){return (Y*y-(ll)((long double)Y/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &Y,ll &y){if(!b)Y=1,y=0;else exgcd(b,a%b,y,Y),y-=Y*(a/b);}
int n,p;
ll A[N];
void cal() {
    ll Y[1205];
    A[0] = A[1] = 1LL;
    Y[0] = 1LL;
    for(int i = 2; i < 1201; i++) {
        Y[i - 1] = A[i - 1];
        for(int j = i - 2; j >= 0; j--)Y[j] = (Y[j] + Y[j + 1])%p;
        A[i] = Y[0]%p;
    }
}
int main(){
    int t;cin>>t;
    while(t--){
        sc("%d%d",&n,&p);
        cal();
        if(n>1200){
            for(int i=1201;i<=n+3;i++)A[i]=(A[i-p]+A[i-p+1])%p;
        }
        printf("%lld\n",A[n]);
    }
}