求逆元 - HNU 13412 Cookie Counter
Cookie Counter
Problem's Link: http://acm.hnu.cn/online/?action=problem&type=show&id=13412&courseid=0
Mean:
将N分为D份，每份不超过X，有多少种分法？
analyse:
首先我们想到的是迭代，但是数据太大，一路迭代下去必定爆栈+超内存+TLE。
我们枚举X，对于满足条件的X，求和统计答案，不满足条件的X，更新往下迭代的P值。最后对P求和即为答案。
这题DP也可以做，不过上面的方法从时间和空间上都大大优于DP。
Time complexity: O(N)
Source code:
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-16-16.39
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
const LL mod = 1000000007;
LL inv[5000];
LL N,X,D;
void pre()
{
inv[1] = 1;
for(int i=2; i<5000; i++)
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
int main()
{
pre();
while(scanf("%d %lld %d",&N,&D,&X) && N)
{
LL ans = 0;
for(int i=0; i*X<=N; i++)
{
LL p = 1;
if(i <= D)
{
for(int j=1; j<=i; j++)
{
p = (D - j + 1) % mod * p % mod;
p = p * inv[j] % mod;
}
}
else p = 0;
for(int j=0; j<i; j++) p = (mod - p);
int gap = N - i*X;
for(int j=1; j<=gap; j++)
{
p = (D + gap - j + mod) % mod * p % mod;
p = p * inv[j] % mod;
}
ans = ans + p;
if(ans >= mod)
ans -= mod;
}
printf("%lld\n",ans);
}
return 0;
}
相关文章：
IEEE 发布年终总结，AI 奇迹不再是故事
编译 | 禾木木 出品 | AI科技大本营（ID:rgznai100） 2021 年，人工智能奇迹不再只是故事！ 人工智能正在迅速融入各行各业，IEEE Spectrum 总结了 2021 年 10 篇最受读者欢迎的 AI 文章，按时间排名，…
一则利用内核漏洞获取root权限的案例【转】
转自：https://blog.csdn.net/u014089131/article/details/73933649 目录(?)[-] 漏洞描述漏洞的影响范围漏洞曝光时间漏洞产生的原因漏洞的利用exploit代码分析kernel 最近出了一个新的本地提权安全漏洞CVE-2013-1763，影响范围比较广泛，ubunt…
Ext.data库
Ext.data 库主要包括以下几个类：Ext.data.Store >DataSetExt.data.Record >DataSet.RowExt.data.DataProxy >SqlConnectionExt.data.DataReader >SqlDataAdapter以下分别进行介绍:1.Ext.data.Record可以用来定义一行数据的格式,它有几个重要的属性和方法…
2021年最有用的数据清洗 Python 库
作者 | 周萝卜来源 | 萝卜大杂烩大多数调查表明，数据科学家和数据分析师需要花费 70-80% 的时间来清理和准备数据以进行分析。对于许多数据工作者来说，数据的清理和准备也往往是他们工作中最不喜欢的部分，因此他们将另外 20-30% 的时间花在抱…
组合与继承之重写方法和字段
为什么80%的码农都做不了架构师？>>> 接上篇blog，scala里的字段和方法属于相同的命名空间，这让字段可以重写无参数方法。例如，你可以通过改变ArrayElement类中contents的实现将其从一个方法变为一个字段，而…
20165334 四则运算阶段性总结（第二周）
四则运算阶段性总结（第二周） 结对对象 学号 ：20165334 姓名 ： 李天龙 担任角色 （驾驶员）：李天龙 （副驾驶）：陈国超 一、实验实现步骤 整数计算类分数计算类自动…
取消掉Transfer-Encoding:chunked
有时候，Web服务器生成HTTP Response是无法在Header就确定消息大小的，这时一般来说服务器将不会提供Content-Length的头信息，而采用Chunked编码动态的提供body内容的长度。进行Chunked编码传输的HTTP Response会在消息头部设置：Tra…
【LeetCode】142 - Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Follow up:Can you solve it without using extra space? Solution： Discuss上的分析：Suppose the first meet at step k,the length of the Cycle …
3000 字详解 Pandas 数据查询，建议收藏
作者 | 俊欣来源 | 关于数据分析与可视化今天小编来和大家说一说怎么从DataFrame数据集中筛选符合指定条件的数据，希望会对读者朋友有所帮助。导入数据集和模块我们先导入pandas模块，并且读取数据，代码如下import pandas as pd df pd.read_c…
stylus使用文档总结：内置方法+参数+条件+迭代+导入+继承
一、内置方法 返回各种颜色的比重（如red(color)等） 颜色函数是CSS预处里器中内置的颜色函数功能，这些功能可以对颜色值进行处理，例如颜色的变亮、变暗、渐变颜色等处理十分的方便。 lighten(color, 10%); /* 返回的颜色在color基础…
用 Python 制作酷炫的可视化大屏，特简单！
作者 | 小F来源 | 法纳斯特在数据时代，我们每个人既是数据的生产者，也是数据的使用者，然而初次获取和存储的原始数据杂乱无章、信息冗余、价值较低。要想数据达到生动有趣、让人一目了然、豁然开朗的效果，就需要借助数据可视化。以…
HTTP协议中的Tranfer-Encoding：chunked编码解析
当不能预先确定报文体的长度时，不可能在头中包含Content-Length域来指明报文体长度，此时就需要通过Transfer-Encoding域来确定报文体长度。通常情况下，Transfer-Encoding域的值应当为chunked,表明采用chunked编码方式来进行报文体的传输。chu…
[转] splice系列系统调用
关注splice系列系统调用（包括splice，tee和vmsplice）已经有一段时间了，开始的时候并未能领会splice的意义所在，致使得出了“splice系列系统调用不怎么实用”的错误结论。随着内核研究的深入，才逐渐懂得&…
嵌入式s5vp210裸机 KXTF9-2050（G-sensor）
1.KXTF9-2050简介 KXTF9-205是G-sensor的一种，G-sensor（Gravity sensor），重力传感器，又名加速度传感器（accelerometer），是能感知加速度大小的MEMS(微机电系统)传感器。使用I2C协议和…
JavaScript面向对象编程
自从有了Ajax这个概念，JavaScript作为Ajax的利器，其作用一路飙升。JavaScript最基本的使用，以及语法、浏览器对象等等东东在这里就不累赘了。把主要篇幅放在如何实现JavaScript的面向对象编程方面。1. 用JavaScript实现类 JavaScritpt没…
sublime text3 前端插件介绍
Emmet插件 Emmet插件可以说是使用Sublime Text进行前端开发必不可少的插件 它让编写HTML代码变得极其简单高效 基本用法：输入标签简写形式，然后按Tab键 关于Emmet的更多介绍，请查看官方文档 这份速查表，可以帮你快速记忆简写形式 …
如何使用 OpenCV Python 检测颜色
作者 | 小白来源 | 小白学视觉在这篇文章中，我们将看到如何使用 Python 中的 OpenCV 模块检测颜色，进入这个领域的第一步就是安装下面提到的模块。pip install opencv-python pip install numpy然后，导入模块。读取图像并使用 OpenCV 模块中的…
使用树形结构保存实体
阅读原文请访问我的博客BrightLoongs Blog之前在项目需要实现一个功能——将xml文件映射成实体，然后对映射的实体进行逻辑处理，最后保存到数据库中；由于xml结构的数据是结构化的数据，所以需要保证保存的数据具有正确的主外键关联。…
在Javascript中使用面向对象的编程
by Mike Koss March 26th, 2003 这是一篇，我个人认为最好的，Javascript面向对象编程的文章。翻译不好的地方，还望大家指正，谢谢。 如果您需要，可以访问下面的地址取得原文： http://mckoss.com/jscript/obj…
马斯克嘲笑「元宇宙」的想法，并给年轻人5条鸡汤
编译 | 禾木木出品 | AI科技大本营（ID:rgznai100）SpaceX 和特斯拉的CEO 马斯克在接受 The Babylon Bee 的采访中，当被问到元宇宙的问题时，马斯克只笑了笑。马斯克表示：“我对元宇宙这个概念没有什么印象，尽…
OpenLDAP自定义属性的启用
2019独角兽企业重金招聘Python工程师标准>>> # ucode# This multivalued field is used to record the values of the license or# registration plate associated with an individual.attributetype ( 2.16.840.1.113730.3.1.900 NAME ucode DESC user code …
硬中断与软中断的区别！
硬中断： 1. 硬中断是由硬件产生的，比如，像磁盘，网卡，键盘，时钟等。每个设备或设备集都有它自己的IRQ（中断请求）。基于IRQ，CPU可以将相应的请求分发到对应的硬件驱动上&am…
smarty模板
<?phprequire(../libs/Smarty.class.php);$smarty new Smarty;//$smarty->force_compile true;//$smarty->debugging true;//$smarty->caching true;//$smarty->cache_lifetime 120;$Name"Linux环境高级编程";$smarty->assign("name&qu…
乘“云原生”之风、踏“数字化”的浪，《新程序员003》开启预售！
12月30日，新年的钟声还有两天敲响，CSDN倾情策划出品的《新程序员003：云原生和全面数字化实践》（以下简称《新程序员003》）重磅开启预售！新一年，新气象~预祝所有开发者在新的一年中大神附体&…
BZOJ4245 : [ONTAK2015]OR-XOR
按位考虑，逐步确定答案。 设当前是第i位，求出第i位的前缀异或和。 若存在m个0且所有数字异或和为0，那么答案的这一位可以为0，并把所有1的位置给标记为不可选。 否则答案的这一位只能是1。 时间复杂度$O(n\log n)$。 #include<c…
关键词排名下降怎么办-优八学院给你支招
优八学院下面为大家解决一下关于关键词排名下降的问题。在我们进行网站优化的时候，往往会出现关键词排名下降的现象。对于这种情况，我们要区别是否是正常的浮动，由于有时候搜索引擎也会发生错误，导致关键词排名下降，我…
全面解析 Kmeans 聚类算法（Python）
作者 | 泳鱼来源 | 算法进阶一、聚类简介Clustering (聚类)是常见的unsupervised learning (无监督学习)方法，简单地说就是把相似的数据样本分到一组（簇），聚类的过程，我们并不清楚某一类是什么（通常无标签信…
.htaccess的重写规则
.htaccess基本语法和应用 .htaccess是Apache服务器的一个非常强大的分布式配置文件。正确的理解和使用.htaccess文件，可以帮助我们优化自己的服务器或者虚拟主机。 如何启用htaccess 以windows为例，进入apache/conf目录，找到httpd.conf文件&a…
amaze ui各个模块简单说明
amaze ui各个模块简单说明 导航添加依据 http://amazeui.org/css/ 下面内容属学习笔记，如有理解偏差和错误请留言相告，感谢！* （官网这块写的很详细） 一、基本样式 1.统一样式 说明了为什么使用Normalize，而…
由浅入深剖析.htaccess
1、.htaccess文件使用前提.htaccess的主要作用就是实现url改写，也就是当浏览器通过url访问到服务器某个文件夹时，作为主人，我们可以来接待这个url，具体地怎样接待它，就是此文件的作用。所有的访问都是通过URL实现&…