草庐IT

马蹄集-2046 巨大的错误

Fortunater 2023-03-28 原文

题目

提瓦特大陆上有一个贫穷的占星术士小码哥，在占星的时候，小码哥时常需要将命运启示他的信息与手中命运之轮上的命星一一对应，现在有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;
}
2046马蹄factorialbig_errorlong算法与数据结构

有关马蹄集-2046 巨大的错误的更多相关文章

  1. ruby-on-rails - Rails 常用字符串(用于通知和错误信息等) - 2

    大约一年前，我决定确保每个包含非唯一文本的Flash通知都将从模块中的方法中获取文本。我这样做的最初原因是为了避免一遍又一遍地输入相同的字符串。如果我想更改措辞，我可以在一个地方轻松完成，而且一遍又一遍地重复同一件事而出现拼写错误的可能性也会降低。我最终得到的是这样的:moduleMessagesdefformat_error_messages(errors)errors.map{|attribute,message|"Error:#{attribute.to_s.titleize}#{message}."}enddeferror_message_could_not_find(obje

  2. ruby-on-rails - 迷你测试错误 : "NameError: uninitialized constant" - 2

    我遵循MichaelHartl的“RubyonRails教程:学习Web开发”，并创建了检查用户名和电子邮件长度有效性的测试(名称最多50个字符，电子邮件最多255个字符)。test/helpers/application_helper_test.rb的内容是:require'test_helper'classApplicationHelperTest在运行bundleexecraketest时，所有测试都通过了，但我看到以下消息在最后被标记为错误:ERROR["test_full_title_helper",ApplicationHelperTest,1.820016791]test

  3. ruby-on-rails - 如何在 Rails View 上显示错误消息？ - 2

    我是rails的新手，想在form字段上应用验证。myviewsnew.html.erb.....模拟.rbclassSimulation{:in=>1..25,:message=>'Therowmustbebetween1and25'}end模拟Controller.rbclassSimulationsController我想检查模型类中row字段的整数范围，如果不在范围内则返回错误信息。我可以检查上面代码的范围，但无法返回错误消息提前致谢 最佳答案 关键是您使用的是模型表单，一种显示ActiveRecord模型实例属性的表单。c

  4. 使用 ACL 调用 upload_file 时出现 Ruby S3 "Access Denied"错误 - 2

    我正在尝试编写一个将文件上传到AWS并公开该文件的Ruby脚本。我做了以下事情:s3=Aws::S3::Resource.new(credentials:Aws::Credentials.new(KEY,SECRET),region:'us-west-2')obj=s3.bucket('stg-db').object('key')obj.upload_file(filename)这似乎工作正常，除了该文件不是公开可用的，而且我无法获得它的公共(public)URL。但是当我登录到S3时，我可以正常查看我的文件。为了使其公开可用，我将最后一行更改为obj.upload_file(file

  5. ruby-on-rails - 错误 : Error installing pg: ERROR: Failed to build gem native extension - 2

    我克隆了一个rails仓库，我现在正尝试捆绑安装背景:OSXElCapitanruby2.2.3p173(2015-08-18修订版51636)[x86_64-darwin15]rails-v在您的Gemfile中列出的或native可用的任何gem源中找不到gem'pg(>=0)ruby​​'。运行bundleinstall以安装缺少的gem。bundleinstallFetchinggemmetadatafromhttps://rubygems.org/............Fetchingversionmetadatafromhttps://rubygems.org/...Fe

  6. ruby - ＃之间？ Cooper 的 *Beginning Ruby* 中的错误或异常 - 2

    在Cooper的书BeginningRuby中，第166页有一个我无法重现的示例。classSongincludeComparableattr_accessor:lengthdef(other)@lengthother.lengthenddefinitialize(song_name,length)@song_name=song_name@length=lengthendenda=Song.new('Rockaroundtheclock',143)b=Song.new('BohemianRhapsody',544)c=Song.new('MinuteWaltz',60)a.betwee

  7. ruby-on-rails - 每次我尝试部署时，我都会得到 - (gcloud.preview.app.deploy) 错误响应 : [4] DEADLINE_EXCEEDED - 2

    我是Google云的新手，我正在尝试对其进行首次部署。我的第一个部署是RubyonRails项目。我基本上是在关注thisguideinthegoogleclouddocumentation.唯一的区别是我使用的是我自己的项目，而不是他们提供的“helloworld”项目。这是我的app.yaml文件runtime:customvm:trueentrypoint:bundleexecrackup-p8080-Eproductionconfig.ruresources:cpu:0.5memory_gb:1.3disk_size_gb:10当我转到我的项目目录并运行gcloudprevie

  8. ruby-on-rails - Rails 5 Active Record 记录无效错误 - 2

    我有两个Rails模型，即Invoice和Invoice_details。一个Invoice_details属于Invoice，一个Invoice有多个Invoice_details。我无法使用accepts_nested_attributes_forinInvoice通过Invoice模型保存Invoice_details。我收到以下错误:(0.2ms)BEGIN(0.2ms)ROLLBACKCompleted422UnprocessableEntityin25ms(ActiveRecord:4.0ms)ActiveRecord::RecordInvalid(Validationfa

  9. arrays - 这是 Ruby 中 Array.fill 方法的错误吗？ - 2

    这个问题在这里已经有了答案:Arraysmisbehaving(1个回答)关闭6年前。是否应该这样，即我误解了，还是错误？a=Array.new(3,Array.new(3))a[1].fill('g')=>[["g","g","g"],["g","g","g"],["g","g","g"]]它不应该导致:=>[[nil,nil,nil],["g","g","g"],[nil,nil,nil]]

  10. ruby-on-rails - Ruby on Rails 计数器缓存错误 - 2

    尝试在我的RoR应用程序中实现计数器缓存列时出现错误Unknownkey(s):counter_cache。我在这个问题中实现了模型关联:Modelassociationquestion这是我的迁移:classAddVideoVotesCountToVideos0Video.reset_column_informationVideo.find(:all).eachdo|p|p.update_attributes:videos_votes_count,p.video_votes.lengthendenddefself.downremove_column:videos,:video_vot

随机推荐