P2822 [NOIP2016 提高组] 组合数问题 题解
又是一道非常水的绿题，真开心，hahaha……
题意解毒
好像没啥好解毒的，直接看思路吧
思路
直接暴力的话想都不用想，直接 T 飞。
我们可以先根据组合恒等式 $C_{n}^{m} = C_{n - 1}^{m - 1} + C_{n}^{m - 1}$ 递推求出所有组合数。因为 $k\mid C_{n}^{m}$ 就相当于 $C_{n}^{m} \equiv 0 \pmod {k}$ ，而且k 是一开始就给定的，这样我们就可以在算组合数的时候就边算边对 $k$ 取模。然后再判断有多少个的值是 $0$ 就行了。
95pts Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3 + 5;
int t, k, m, n, c[N][N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> t >> k;
for (int i = 0; i <= 2e3; i++)
{
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
}
while (t--)
{
int ans = 0;
cin >> n >> m;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= min(i, m); j++)
ans += c[i][j] == 0;
cout << ans << "\n";
}
}
|
TLE 了？！
该算法时间复杂度是 $O(max(n)^2)$ ，算上查询倍数是 $O(tmax(n)^2)$,TLE 很正常吧。能得到 95pts 已经很不错了，说明数据太水了 。
正解
思考如何优化。
我们可以发现要求得的答案是一个区间中的 $0$ 的数量，所以可以很自然的想到用二维差分来优化查询效率。
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3 + 5;
int t, k, m, n, c[N][N], sum[N][N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> t >> k;
for (int i = 0; i <= 2e3; i++)
{
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
}
for (int i = 1; i <= 2e3; i++)
for (int j = 1; j <= 2e3; j++)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (c[i][j] == 0 && j <= i);
while (t--)
{
cin >> n >> m;
cout << sum[n][min(n, m)] << "\n";
}
}
|
