#include<cstdio>
#define rec(x,y) rec[aa[y]+x]
using namespace std;

int n,m,a,b,c,p,l1,l2,l3,l0;
int rec[100000001],ans=0,aa[10001],f[255];
int main(){
    scanf("%d%d%d%d%d%d",&m,&p,&n,&a,&b,&c);
    register int i,j;
    if (n>m) n=m;
    aa[1]=0;
    a%=p;b%=p;c%=p;
    f[0]=c;
    for (i=1;i<p;i++){
        f[i]=f[i-1]+a*(2*i-1)+b;
        while (f[i]>=p) f[i]-=p;
    }
    for (i=2;i<=m;i++) aa[i]=aa[i-1]+i-1;
    for (i=1,j=1;i<=m;i++,j++,j-=j>=p?p:0)
    if (i>p) rec(1,i)=rec(1,(j==0?p-1:j-1)+1);else rec(1,i)=f[j];
    int k=((rec(1,2)-3*rec(1,1))+3*p)%p,y=(2*a-rec(1,2)+2*rec(1,1)+100*p)%p;
    ans=rec(1,m);
    for (i=2;i<=n;i++){
        rec(i,i)=(rec(i-1,i-1)*f[1])%p;
        int d=rec(i,i);
        j=i+1;
        d+=((k*rec(i-1,j-2))+(f[1]*rec(i-1,j-1)));
        rec(i,j)=(2*rec(i,j-1)+d+p)%p;
        j++;
        l0=aa[j]+i;l1=aa[j-1]+i-1;l2=aa[j-2]+i-1;l3=aa[j-3]+i-1;
        for (;j<=m;j++){
            d+=((y*rec[l3])+(k*rec[l2])+(f[1]*rec[l1]));
            rec[l0]=(2*rec[l1+1]-rec[l2+1]+d+p)%p;
            l0+=j;l1+=j-1;l2+=j-2;l3+=j-3;
        }
        ans+=rec(i,m);
    }
    printf("%d\n",ans%p);
}```



























ac全靠rp
测试数据 #0: Accepted, time = 0 ms, mem = 391936 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 391936 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 391932 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 391932 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 391940 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 391936 KiB, score = 10
测试数据 #6: Accepted, time = 328 ms, mem = 391936 KiB, score = 10
测试数据 #7: Accepted, time = 328 ms, mem = 391936 KiB, score = 10
测试数据 #8: Accepted, time = 984 ms, mem = 391932 KiB, score = 10
测试数据 #9: Accepted, time = 1000 ms, mem = 391936 KiB, score = 10
Accepted, time = 2655 ms, mem = 391940 KiB, score = 100
代码
```c++
#include<cstdio>
#define rec(x,y) rec[aa[y]+x]
using namespace std;

int n,m,a,b,c,p,l1,l2,l3,l0;
int rec[100000001],ans=0,aa[10001],f[255];
int main(){
    scanf("%d%d%d%d%d%d",&m,&p,&n,&a,&b,&c);
    register int i,j;
    if (n>m) n=m;
    aa[1]=0;
    a%=p;b%=p;c%=p;
    f[0]=c;
    for (i=1;i<p;i++){
        f[i]=f[i-1]+a*(2*i-1)+b;
        while (f[i]>=p) f[i]-=p;
    }
    for (i=2;i<=m;i++) aa[i]=aa[i-1]+i-1;
    for (i=1,j=1;i<=m;i++,j++,j-=j>=p?p:0)
    if (i>p) rec(1,i)=rec(1,(j==0?p-1:j-1)+1);else rec(1,i)=f[j];
    int k=((rec(1,2)-3*rec(1,1))+3*p)%p,y=(2*a-rec(1,2)+2*rec(1,1)+100*p)%p;
    ans=rec(1,m);
    for (i=2;i<=n;i++){
        rec(i,i)=(rec(i-1,i-1)*f[1])%p;
        int d=rec(i,i);
        j=i+1;
        d+=((k*rec(i-1,j-2))+(f[1]*rec(i-1,j-1)));
        rec(i,j)=(2*rec(i,j-1)+d+p)%p;
        j++;
        l0=aa[j]+i;l1=aa[j-1]+i-1;l2=aa[j-2]+i-1;l3=aa[j-3]+i-1;
        for (;j<=m;j++){
            d+=((y*rec[l3])+(k*rec[l2])+(f[1]*rec[l1]));
            rec[l0]=(2*rec[l1+1]-rec[l2+1]+d+p)%p;
            l0+=j;l1+=j-1;l2+=j-2;l3+=j-3;
        }
        ans+=rec(i,m);
    }
    printf("%d\n",ans%p);
}```