开发笔记:IrrelevantElementsUVA1635（二项式定理）

作者：手机用户2502894791 | 来源：互联网 | 2023-09-17 10:58

vjudge链接原题链接乍一看似乎没什么思路，但是写几个简单的例子之后规律就变得很明显。比如当n=5时，每一步计算后

vjudge链接

原题链接

乍一看似乎没什么思路，但是写几个简单的例子之后规律就变得很明显。

比如当 n=5 时，每一步计算后的结果如下：

a₁

a₁+a₂

a₁+2a₂+a₃

a₁+3a₂+3a₃+a₄

a₁+4a₂+6a₃+4a₄+a₅

显然系数“1, 4, 6, 4, 1”就是杨辉三角第五行。

故某一项的系数是否是题中 m 的倍数，就决定了最终得到的数除以 n 的余数和那一项是否有关。

二项式定理：

技术图片

从中很容易得到前后两项的关系 C(n, k)=(n-k+1)/k*C(n, k-1) 。但是单纯用这个公式暴力得到每个系数一定会导致溢出，故需要运用唯一分解定理分别存储每个系数的素因数和指数。

一般的代码不难给出，但是一直TLE。最后发觉应该先分解 m ，再得到 m 的素因数在各个 C(n,k) 中的指数，若指数过小则可以提前结束当前的分解。由于 m>1 ，可以忽略 n==k 和 n==0 的情况。

我的 AC 代码如下，最初是用 ANSI C 写的，一步一步改过来，故非常不简洁。其中用 map 存储素因数，其中元素 -1 用来作为该项是否能被 m 整除的 flag。

/* *lang C++ 5.3.0 *user Weilin_C */ #include #include #include #include #include #include <iostream> #include #include #include #include #include //#include #include #include #include //每个数用map分质因数存储 //质数用素数筛 2-1000000000, MAXM=1000000 #define MAXM 1000000 #define MAXN 100000+5 using namespace std; map sta[MAXN], mm; int pos[MAXN]; int prime[MAXM+1]; void mtomap (map *ma, int n, int p) { //解码m n: 解码的数 p: 数n的个数 int num=n; for (int i=2; i<=MAXM && num>0; i++) { if (!prime[i]) { while (num%i==0 && num>0) { num/=i; (*ma).insert(pair(i, 0)); (*ma)[i]+=p; } } } if (num>1) (*ma).insert(pair(num, 1)); return; } void ntomap (map *ma, int n, int p) { //用于逐个解码第n行的杨辉三角 n: 解码的数 p: 数n的个数 map ::iterator it; int num=n, t; if (n<2) return; for (it=mm.begin(); it!=mm.end(); it++) { t=it->first; if (t<2) continue; (*ma).insert(pair(t, 0)); while (num%t==0 && num>0) { num/=t; (*ma)[t]+=p; } if ((*ma)[t]second) (*ma)[-1]=0; } return; } int judge(map *ma) { //是否为0或1 int flag=0; map ::iterator it; for (it=(*ma).begin(); it!=(*ma).end(); it++) if (it->second!=0 && it->first!=-1) { flag=1; break; } return flag; } int main() { int m, n; //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); /* C(n, k) = (n-k+1)/k * C(n, k-1) */ for (int i=2; i<=sqrt(MAXM+1); i++) { if (prime[i]) continue; for (int j=i+i; j<=MAXM; j+=i) prime[j]=1; } while (scanf("%d%d", &n, &m)==2) { //n: 杨辉三角层数 //printf("%d %d ", n, m); for (int i=0; i<=n; i++) if (!sta[i].empty()) sta[i].clear(); mm.clear(); sta[0][m]=0; sta[0][-1]=0; mtomap(&mm, m, 1); map ::iterator it; for (int i=1; i for (it=sta[i-1].begin(); it!=sta[i-1].end(); it++) sta[i][it->first]=it->second; sta[i][-1]=1; ntomap(&sta[i], n-i, 1); ntomap(&sta[i], i, -1); } pos[0]=0; int ans=0; for (int i=0; i if (sta[i][-1] && judge(&sta[i])) { ans++; pos[++pos[0]]=i+1; } } printf("%d ", ans); int f=0; for (int i=1; i<=pos[0]; i++) { if (f) putchar(&＃39; &＃39;); else f=1; printf("%d", pos[i]); } putchar(&＃39; &＃39;); } return 0; }

by SDUST weilinfox

本文链接：https://www.cnblogs.com/weilinfox/p/12241600.html

推荐阅读

object
STL迭代器的种类及其功能介绍

本文介绍了标准模板库(STL)定义的五种迭代器的种类和功能。通过图表展示了这几种迭代器之间的关系，并详细描述了各个迭代器的功能和使用方法。其中，输入迭代器用于从容器中读取元素，输出迭代器用于向容器中写入元素，正向迭代器是输入迭代器和输出迭代器的组合。本文的目的是帮助读者更好地理解STL迭代器的使用方法和特点。 ... [详细]

蜡笔小新 2023-12-10 15:17:25
object
C++ STL复习（13）容器适配器

STL提供了3种容器适配器，分别为stack栈适配器、queue队列适配器以及priority_queue优先权队列适配器。不同场景下，由于不同的序列式 ... [详细]

蜡笔小新 2023-10-17 18:15:36
object
一文了解Python collections模块中的deque用法[python头条资讯]

Python中文网有大量免费的Python入门教程，欢迎大家来学习。collections是Python内建的一个集合模块，deque是双边队列，具有队列和栈的性质，在list的基 ... [详细]

蜡笔小新 2023-10-16 14:22:02
ip
C#学习教程：在Console中工作但在Windows窗体中不工作的异步代码分享

本文分享了一个关于在C#中使用异步代码的问题，作者在控制台中运行时代码正常工作，但在Windows窗体中却无法正常工作。作者尝试搜索局域网上的主机，但在窗体中计数器没有减少。文章提供了相关的代码和解决思路。 ... [详细]

蜡笔小新 2023-12-14 15:56:00
default
Java容器中的compareto方法排序原理解析

本文从源码解析Java容器中的compareto方法的排序原理，讲解了在使用数组存储数据时的限制以及存储效率的问题。同时提到了Redis的五大数据结构和list、set等知识点，回忆了作者大学时代的Java学习经历。文章以作者做的思维导图作为目录，展示了整个讲解过程。 ... [详细]

蜡笔小新 2023-12-14 13:53:31
default
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
default
关于cuowu类的错误提示和使用AdjustmentListener的问题

本文讨论了一个关于cuowu类的问题，作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案，并给出了两个可能导致错误的原因。 ... [详细]

蜡笔小新 2023-12-13 22:09:56
object
SpringJdbcTemplate的使用详解

本文详细介绍了Spring的JdbcTemplate的使用方法，包括执行存储过程、存储函数的call()方法，执行任何SQL语句的execute()方法，单个更新和批量更新的update()和batchUpdate()方法，以及单查和列表查询的query()和queryForXXX()方法。提供了经过测试的API供使用。 ... [详细]

蜡笔小新 2023-12-13 14:27:11
request
深入理解Kafka服务端请求队列中请求的处理

本文深入分析了Kafka服务端请求队列中请求的处理过程，详细介绍了请求的封装和放入请求队列的过程，以及处理请求的线程池的创建和容量设置。通过场景分析、图示说明和源码分析，帮助读者更好地理解Kafka服务端的工作原理。 ... [详细]

蜡笔小新 2023-12-12 16:14:59
request
hdu 5439（找规律）的数列求和问题

本文讨论了一个数列求和问题，该数列按照一定规律生成。通过观察数列的规律，我们可以得出求解该问题的算法。具体算法为计算前n项i*f[i]的和，其中f[i]表示数列中有i个数字。根据参考的思路，我们可以将算法的时间复杂度控制在O(n)，即计算到5e5即可满足1e9的要求。 ... [详细]

蜡笔小新 2023-12-12 14:05:58
request
李逍遥寻找仙药的迷阵之旅

本文讲述了少年李逍遥为了救治婶婶的病情，前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵，有些方格内有怪物，有些方格是安全的。李逍遥需要避开有怪物的方格，并经过最少的方格，找到仙药。在寻找的过程中，他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]

蜡笔小新 2023-12-12 13:59:33
request
重入锁（ReentrantLock）学习及实现原理

本文介绍了重入锁（ReentrantLock）的学习及实现原理。在学习synchronized的基础上，重入锁提供了更多的灵活性和功能。文章详细介绍了重入锁的特性、使用方法和实现原理，并提供了类图和测试代码供读者参考。重入锁支持重入和公平与非公平两种实现方式，通过对比和分析，读者可以更好地理解和应用重入锁。 ... [详细]

蜡笔小新 2023-12-11 15:16:28
request
Codeforces Round #321 (Div. 2) Kefa and Dishes 状压+spfa

本文介绍了Codeforces Round #321 (Div. 2)比赛中的问题Kefa and Dishes，通过状压和spfa算法解决了这个问题。给定一个有向图，求在不超过m步的情况下，能获得的最大权值和。点不能重复走。文章详细介绍了问题的题意、解题思路和代码实现。 ... [详细]

蜡笔小新 2023-12-11 10:37:34
request
Codeforces Round #383 (Div. 2) D 分组背包

给出一群女孩的重量和颜值和她们的朋友关系现在有一个舞台ab是朋友bc是朋友ac就是朋友给出最大承重可以邀请这些女孩来玩对于每一个朋友团体全邀请or邀请一个or不邀请问能邀请的女孩的 ... [详细]

蜡笔小新 2023-10-17 17:22:42
ip
如何在运行参数中导入txt文件

刚开始crousera上学习<algorithmspart1>但对JAVA实在是不熟。******************************************** ... [详细]

蜡笔小新 2023-10-16 18:10:03

手机用户2502894791

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章