BZOJ3612 [HEOI2014]平衡

2015.01.10 12:04 Sat| 2 visits oi_2015| 2015_刷题日常| Text

Problem

Description

下课了,露露、花花和萱萱在课桌上用正三棱柱教具和尺子摆起了一个“跷跷板”。这个“跷跷板”的结构是这样的:底部是一个侧面平行于地平面的正三棱柱教具,上面摆着一个尺子,尺子上摆着若干个相同的橡皮。尺子有 2n + 1 条等距的刻度线,第 n + 1 条刻度线恰好在尺子的中心,且与正三棱柱的不在课桌上的棱完全重合。

露露发现这个“跷跷板”是不平衡的(尺子不平行于地平面)。于是,她又在尺子上放了几个橡皮,并移动了一些橡皮的位置,使得尺子的 2n + 1 条刻度线上都恰有一块相同质量的橡皮。“跷跷板”平衡了,露露感到很高兴。

花花觉得这样太没有意思,于是从尺子上随意拿走了 k 个橡皮。令她惊讶的事情发生了:尺子依然保持着平衡!

萱萱是一个善于思考的孩子,她当然不对尺子依然保持平衡感到吃惊,因为这只是一个偶然的事件罢了。令她感兴趣的是,花花有多少种拿走 k 个橡皮的方法,使得尺子依然保持平衡?当然,为了简化问题,她不得不做一些牺牲——假设所有橡皮都是拥有相同质量的质点。但即使是这样,她也没能计算出这个数目。放学后,她把这个问题交给了她的哥哥/姐姐——Hibarigasaki 学园学生会会长,也就是你。当然,由于这个问题的答案也许会过于庞大,你只需要告诉她答案 mod p 的值。

Input

第一行,一个正整数,表示数据组数 T(萱萱向你询问的次数)。

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

Output

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

Sample I/O

balance.in

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

balance.out

73

1

920

81

4421

2565

0

446

2549

Hint

10%的数据满足: n <= 10。

30%的数据满足: n <= 50。

50%的数据满足: n <= 1000。

另有 10%的数据满足: k = 3。

在此基础上,另有 10%的数据满足: p = 2。

100%的数据满足: T <= 20, 1 <= n <= 10000, 1 <= k <= 10, 2 <= p <= 10000,且 k <= 2n+1。

Solution

显然,若两边拿走橡皮的力矩之和相等,即距离重心的距离之和相等,则尺子可以达到平衡。

枚举一侧的距离之和,再枚举一侧的橡皮数目 i,则另一侧橡皮数目可能的情况有 k-i 和 k-i-1 两种。分别计算情况数,将两侧可能的情况数目的乘积计入答案。

于是问题转化为:给定一个正整数 i ,求将 i 划分成 j 个互不相同且均不大于 n 的正整数的情况数。

由整数划分的原理,不考虑不大于 n 这一条件的情况下, $f_{i, j} = f_{i-j, j-1} + f_{i-j, j}$ 。加上这一条件实质上就是减少了在 n 的基础上加 1 这一种情况,因此只需减去 $f_{i, j} = f_{i-n-1, j-1}$ 即可得到真正的答案。

Code

#include <bits/stdc++.h>
using namespace std;

int t, n, k, p, f[200005][22], tot;

int main()
{
    cin >> t;
    while (t--)
    {
        scanf("%d%d%d", &n, &k, &p); tot = 0;
        if (k == 1) { puts("1"); continue; }
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; ++i)
            f[i][1] = 1;
        for (int i = n; i >= max(0, n - k); --i)
            tot += i;
        for (int i = 1; i <= tot; ++i)
            for (int j = 2; j <= min(k, i); ++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] = (f[i][j] % p + p) % p;
            }
        long long ans = 0;
        for (int i = 1; i <= tot; ++i)
            for (int j = 1; j < k; ++j)
                ans = (ans + 1ll * f[i][j] * f[i][k-j]) % p;
        for (int i = 1; i <= tot; ++i)
            for (int j = 1; j < k; ++j)
                ans = (ans + 1ll * f[i][j] * f[i][k-j-1]) % p;
        printf("%lld\n", ans);
    }
    return 0;
}