【算法随记】C(n,m)不越界但A(n,m)越界;

这篇具有很好参考价值的文章主要介绍了【算法随记】C(n,m)不越界但A(n,m)越界;。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

https://codeforces.com/contest/893/problem/E

C(n,m)不越界但A(n,m)越界的解决方案

C(n,m) = A(n,m) / (n-m)!

这题要模1e9+7,但是只有加减乘能模,除法模不了。所以这个A(n,m)要存原值,原值也太大了,爆 long long

要是能不要除法,全是乘法就好了

法一:拆成多个质数相乘

先算A(n,m)里有多少个2 3 5 7,再减去(n-m)!中2 3 5 7的个数,最后把剩下的乘起来文章来源地址https://www.toymoban.com/news/detail-667401.html

long long C(int n, int m){
   
    long long ret=1;
 
    unordered_map<int,int> table;
    for(int x=n;x>m;x--){
   
        int tmpx=x;
        for(int i=2;i<=tmpx;i++){
   
            if(tmpx%i==0){
   
                int tmpcnt=1;
                tmpx=tmpx/i;
                while(tmpx%i==0 && tmpx){
   
                    tmpcnt++;
                    tmpx/=i;
                }
                table[i]+=tmpcnt;
            }
        }
    }
    for(int x=n-m;x>=1;x--){
   
        int tmpx=x;
        for(int i=2;i<=tmpx;i++){
   
            if(tmpx%i==0){
   
                int tmpcnt=1;
                tmpx=tmpx/i;
                while(tmpx%i==0 && tmpx){
   
                    tmpcnt++;
                    tmpx/=i;
                }
                table[i]-=tmpcnt;
            }
        }
    }
 
    for(auto it=table.begin(); it!=table.end();it++){
   
        int x=it->first;
        int cnt=it->second;

到了这里,关于【算法随记】C(n,m)不越界但A(n,m)越界;的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法随记】二进制数的后缀相同不代表它们是倍数关系

    https://codeforces.com/contest/893/problem/B 第三个点是81142,wa了 打出来看是01101111001111001(倒序),我的输出是6(110),感觉没问题呀,正好是最后面的三位 傻了 110xxxxxx不是110的倍数,xxxxxx110也不是 就像7xxx未必是7的倍数,xxxx7也未必是7的倍数 只有xxxxx10是10的倍数,xxxxx1是1的倍数

    2024年02月12日
    浏览(42)
  • 内存越界是否一定会导致程序崩溃吗?详解内存越界

    目录   1、什么是内存越界? 1.1、对数组的读越界  1.2、执行strcpy时的写越界 

    2024年02月03日
    浏览(46)
  • 关注潜在的整数越界问题

    在平时的开发过程中,整数越界是一个容易被忽视的问题,关注潜在的整数越界问题可使我们编写的代码更加健壮,规避因整数越界导致的 bug。 以下是在 Code Review 中发现的 比较器 实现: 乍一看该比较器实现不存在问题,但是如果 tag1 = Integer.MIN_VALUE = -2147483648, tag2 为大于

    2024年02月05日
    浏览(43)
  • java.lang.ArrayIndexOutOfBoundsException: (数组越界异常)

    在刚入门Java编程的时候,我们经常会遇到数组越界异常的问题。 当我们访问数组中不存在的索引位置时,就会触发这个异常。 数组基础知识回顾: 首先,我们需要了解一些数组的基础知识。在Java中,数组是一种用于存储多个相同类型数据的数据结构。我们可以通过定义、

    2024年02月08日
    浏览(44)
  • Nginx越界读取缓存漏洞(CVE-2017-7529)

    注意:仅用于技术讨论,切勿用于其他用途,一切后果与本人无关!!! 理论知识         The Range 是一个请求首部,告知服务器返回文件的哪一部分。在一个 Range 首部中,可以一次性请求多个部分,服务器会以 multipart 文件的形式将其返回。如果服务器返回的是范围响应

    2024年02月16日
    浏览(43)
  • Java语言开发在线小说推荐网 小说推荐系统 基于用户、物品的协同过滤推荐算法 SSM(Spring+SpringMVC+Mybatis)开发框架 大数据、人工智能、机器学习开发

    1、开发工具和使用技术 MyEclipse10/Eclipse/IDEA,jdk1.8,mysql5.5/mysql8,navicat数据库管理工具,tomcat,SSM(spring+springmvc+mybatis)开发框架,jsp页面,javascript脚本,jquery脚本,bootstrap前端框架(用户端),layui前端框架(管理员端),layer弹窗组件等。 2、实现功能 前台用户包含:注

    2023年04月26日
    浏览(84)
  • Cadence&Allegro随记02

    WARNING(ORCAP-1600): Net has fewer than two connections XXX WARNING(ORCAP-1611): Two nets in same schematic have the same name, but there is no off-page connector XXX WARNING(ORCAP-36006): Part Name “EL3H7-G_4PIN_SOP-4_L4_4-W2_8-P1_27-LS7_0-TL_EL3H7-G_4PIN” is renamed to “EL3H7-G_4PIN_SOP-4_L4_4-W2_8-P1”. ERROR(SPMHGE-82): Pin numbers do not match be

    2024年02月04日
    浏览(41)
  • jmeter随记2:压测

    简述 关于压测,jmeter更直观的作用是用来编写压测脚本【请求和压测策略】,然后在linux服务器上执行,也可以在本地执行,压测执行脚本在启动jmeter服务的时候,会打印出执行压测的命令 一、压测步骤 step1: 编写jmeter脚本,以及压测策略 a、若想压的接口很多 且都是相同域

    2024年02月15日
    浏览(33)
  • 【问题随记】

    ubuntu 14.04源更新(sources.list) deb http://mirrors.aliyun.com/ubuntu/ trusty main restricted universe multiverse deb http://mirrors.aliyun.com/ubuntu/ trusty-security main restricted universe multiverse deb http://mirrors.aliyun.com/ubuntu/ trusty-updates main restricted universe multiverse deb http://mirrors.aliyun.com/ubuntu/ trusty-proposed m

    2024年02月14日
    浏览(37)
  • 机器学习随记(1)

    损失函数(Loss Function )是定义在单个样本上的,算的是一个样本的误差。 代价函数(Cost Function )是定义在整个训练集上的,是所有样本误差的平均,也就是损失函数的平均。 目标函数(Object Function)定义为:最终需要优化的函数。等于经验风险+结构风险(也就是代价函数

    2024年02月02日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包