题解 P1595 【信封问题】
题解 P1595 【信封问题】
杨戬大师
·
2019-08-29 15:06:23
·
题解
这道题我一上来就开始思考每一组数据之间的关系，如果发现了关系，就可以通过递推的方式求出答案了。
假如现在有 n 个信封和信，那么我把答案记为 Sn。不难发现这个Sn是这样构成的：先是不管每一个信装没装错，那么一共有 n! 种组成方式。但是这 n! 显然多了，那么我就减掉那些多的。
这是求 n! 的代码：
long long jc(int x)
{
long long ans = 1, i;
for (i = 2; i <= x; i++)
ans *= i;
return ans;
}
那么多的是如何构成的呢？多的是有一些信封的位置是对的，而剩下的是错的。所以不管那些对的，那些错的有多少种组成方式我们之前已经算出来了！只不过它们有可能再一些不同的位置上，所以我们再在每个 Sn-1 到 S1 前面乘一个系数，这系数便是它有可能在几种位置上，用一个排列组合中的组合就行了。其实就是那个我们所熟知的C。
求组合C的代码：
long long C(int x, int y)//组合函数
{
long long ans = 1, i;
y = min(y, x - y);
for (i = x; i > x - y; i--)
ans *= i;
for (i = y; i > 0; i--)
ans /= i;
return ans;
}
按如上方法算完多的以后，就用 n! 减去那些多的，便是每一层的答案了，然后再一路递推，就可以推出答案了。
感觉我说的不太清楚，可以看看代码是如何写的。
AC代码：
#include
#include
using namespace std;
long long jc(int x)
{
long long ans = 1, i;
for (i = 2; i <= x; i++)
ans *= i;
return ans;
}
long long C(int x, int y)//组合函数
{
long long ans = 1, i;
y = min(y, x - y);
for (i = x; i > x - y; i--)
ans *= i;
for (i = y; i > 0; i--)
ans /= i;
return ans;
}
long long s[21];
int main()
{
int n, i, j;
scanf("%d", &n);
for (i = 2; i <= n; i++)
{
s[i] = jc(i) - 1;
for (j = i - 1; j > 1; j--)
s[i] -= s[j] * C(i, j);
}
printf("%lld", s[n]);
return 0;
}