BZOJ 3612: [Heoi2014]平衡( dp )

时间：2022-02-20 21:09:43

BZOJ 3612: [Heoi2014]平衡( dp )

枚举Fl, 就变成一个整数划分的问题了...f(i,j) = f(i-j,j-1)+f(i-j,j)-f(i-N-1,j-1)递推。f(i,j)表示数i由j个不同的数组成，且最大不超过N的方案数

--------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
const int maxn = 10009;
const int maxk = 19;
 
int MOD, N, K;
int f[maxn * maxk][maxk];
 
void upd(int &t, int d) {
if((t += d) >= MOD)
t -= MOD;
}
 
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d%d", &N, &K, &MOD);
memset(f, 0, sizeof f);
f[0][0] = 1;
for(int i = 1, lim = N * K; i < lim; i++)
for(int j = 1; j <= min(i, K); j++) {
f[i][j] = f[i - j][j - 1] + f[i - j][j];
if(i > N)
f[i][j] -= f[i - N - 1][j - 1];
f[i][j] += MOD;
while(f[i][j] >= MOD)
f[i][j] -= MOD;
}
int ans = 0;
for(int i = 1, lim = N * K; i < lim; i++)
for(int j = 1; j < K; j++) {
upd(ans, f[i][j] * f[i][K - j] % MOD);
if(j > 1)
upd(ans, f[i][j - 1] * f[i][K - j] % MOD);
}
if(K == 1)
ans = 1;
printf("%d\n", ans);
}
return 0;
}

--------------------------------------------------------------------------

3612: [Heoi2014]平衡

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 173  Solved: 126
[Submit][Status][Discuss]

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。

Source

相关文章