马蹄集-2046 巨大的错误
2023-04-18 15:27:00 时间
题目
提瓦特大陆上有一个贫穷的占星术士小码哥,在占星的时候,小码哥时常需要将命运启示他的信息与手中命运之轮上的命星一一对应,现在有n
个启示和n
个命星需要一一对应,有时,因为命运实在太过难以言明,小码哥会将所有的启示与命星都对应错了,此时称小码哥犯了一个巨大的错误,问一共有多少种情况可被称为“巨大的错误”。
格式
输入格式:输入一个正整数n
(n <= 20)
输出格式:输出一个正整数代表所求答案
样例
输入:2
输出:1
思路
第一想法就是平常做概率题的思路,使用所有情况减去至少一个正确的情况,得到的就是全部都错位的情况。
至少正确一个的情况会分为:只正确一个的情况、只正确两个的情况...全部正确的情况
但是会发现,这些情况直接使用排列组合不好算出来;但是这里面的每一种情况都会取决于相同问题,但是n-1的输入,使用下面的例子来说明:
我们之来看只有一个正确的情况:
假设有n个点,并给他们编号为1...n,全部正确的序列就应该是:1...n。
我们现在需要求只有一个点编号正确的情况,那么我们先固定点1的编号是正确的,那么剩下的n-1个节点的序列都应该是全部错乱的,那就变成了同样的问题,但是输入为n-1的问题了
而我们可以固定的点有n个,所以只有一个正确的情况有:n * F(n-1)
(假设该问题的求解函数为F)
经过总结可以得到通式:
[F(n) = n! - sum_{i=1}^nC_n^iF(n-i)
]
代码
#include<bits/stdc++.h>
using namespace std;
unordered_map<int , long long> big_error; // 全部错位的情况
unordered_map<int , long long> factorial; // 可能用到的阶乘
void storage_factorial(int n){
long long ans = 1;
factorial[0] = 1;
factorial[1] = 1;
for (int i = 2; i <= n; ++i) {
ans *= i;
factorial[i] = ans;
}
}
// 组合数公式计算
long long cal_C(int n, int i) {
return factorial[n] / ( factorial[n-i] * factorial[i]);
}
// 上述的F函数
long long solution(int n) {
if (big_error.count(n)) return big_error[n]; // 如果之前计算或者保存过就直接返回
long at_least_right = 0; // 至少对一个的所有情况
for (int i=1; i<=n; ++i) {
at_least_right += cal_C(n, i) * solution(n-i);
}
big_error[n] = factorial[n] - at_least_right;
return big_error[n];
}
int main( )
{
int n;
cin >> n;
big_error[0] = 1;
big_error[1] = 0;
big_error[2] = 1;
storage_factorial(n);
cout << solution(n) << endl;
return 0;
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击