开发者社区云计算文章正文

MT2046 巨大的错误

2024-05-24 48

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： MT2046 巨大的错误

1.暴力代码 2/10

#include <bits/stdc++.h>
using namespace std;
int n;
int a[25];
int b[25];
int ans = 0;
bool err()
{
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == b[i])
        {
            return false;
        }
    }
    return true;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        a[i] = i;
        b[i] = i;
    }
    do
    {
        do
        {
            if (err())
            {
                ans++;
            }
        } while (next_permutation(b + 1, b + n + 1));
    } while (next_permutation(a + 1, a + n + 1)); // 求全排列
    cout << ans / n;
}

2.使用了组合数学里的错排公式

错排公式：n个编号和n个位置全部不对应。M(n)=(n-1)[M(n-2)+M(n-1)]

M(1)=0，M(2)=1。

所以在写代码的时候，a[0]=0,a[1]=0,a[2]=1.

注意点：错排公式，开long long

#include <bits/stdc++.h>
using namespace std;
long long int n;
long long int a[25];
int main()
{
    cin >> n;
    a[0] = 0;
    a[1] = 0;
    a[2] = 1;
    for (long long int i = 3; i <= n; i++)
    {
        a[i] = (i - 1) * (a[i - 2] + a[i - 1]);
    }
    cout << a[n];
    return 0;
}