【递推】Bzoj3612[Heoi2014]平衡

2024-03-09 12:27:05

Description

下课了，露露、花花和萱萱在课桌上用正三棱柱教具和尺子摆起了一个“跷跷板”。

这个“跷跷板”的结构是这样的：底部是一个侧面平行于地平面的正三棱柱教具，

上面摆着一个尺子，尺子上摆着若干个相同的橡皮。尺子有 2n + 1 条等距的刻度线，

第 n + 1 条刻度线恰好在尺子的中心，且与正三棱柱的不在课桌上的棱完全重合。

露露发现这个“跷跷板”是不平衡的（尺子不平行于地平面）。于是，她又在尺

子上放了几个橡皮，并移动了一些橡皮的位置，使得尺子的 2n + 1 条刻度线上都恰

有一块相同质量的橡皮。“跷跷板”平衡了，露露感到很高兴。

花花觉得这样太没有意思，于是从尺子上随意拿走了 k 个橡皮。令她惊讶的事

情发生了：尺子依然保持着平衡！

萱萱是一个善于思考的孩子，她当然不对尺子依然保持平衡感到吃惊，因为这

只是一个偶然的事件罢了。令她感兴趣的是，花花有多少种拿走 k 个橡皮的方法

，使得尺子依然保持平衡？

当然，为了简化问题，她不得不做一些牺牲——假设所有橡皮都是拥有相同质量的

质点。但即使是这样，她也没能计算出这个数目。放学后，她把这个问题交给了她

的哥哥/ 姐姐——Hibarigasaki 学园学生会会长，也就是你。当然，由于这个问题

的答案也许会过于庞大，你只需要告诉她答案 mod p 的值。

Input

第一行，一个正整数，表示数据组数 T（萱萱向你询问的次数）。

接下来 T 行，每行 3 个正整数 n, k, p。

Output

共 T 行，每行一个正整数，代表你得出的对应问题的答案。

Sample Input

10
6 5 10000
4 1 10000
9 6 10000
4 6 10000
5 1 10000
8318 10 9973
9862 9 9973
8234 9 9973
9424 9 9973
9324 9 9973

Sample Output

73
1
920
8
1
4421
2565
0
446
2549

HINT

T <= 20，1 <= n <= 10000，1 <= k <= 10，2 <= p <= 10000，且 k <= 2n+1。

设f[i][j]表示用j个数组成i，那么可以由f[i-j][j]+f[i-j][j-1]得到。

转移后最大元素可能>n，但只可能为n+1，于是直接去掉这个数，减去f[i-n-1][j-1]。

都减一的转移思路还是蛮好的。

#include<cstdio>

const int maxn=1e5+;

int f[maxn][];

int t,n,k,p;

int main(){

    scanf("%d",&t);

    while(t--){

        scanf("%d%d%d",&n,&k,&p);

        f[][]=;

        for(int i=;i<=n*k;i++)

            for(int j=;j<=i&&j<=k;j++){

                f[i][j]=(f[i-j][j]+f[i-j][j-])%p;

                if(i>=n+) f[i][j]=((f[i][j]-f[i-n-][j-])%p+p)%p;

            }

        int ans=;

        for(int i=;i<=k;i++)

            for(int j=;j<=n*k;j++){

                ans+=(f[j][i]*f[j][k-i]),ans%=p;

                if(i<k) ans+=(f[j][i]*f[j][k-i-]),ans%=p;

            }

        printf("%d\n",ans);

    }

    return ;

}