正文

hdu6467简单数学题递推公式&&o优化乘法（广东工业大学第十四届程序设计竞赛）(代码片段)

ymzjj  ymzjj  2023-03-09  238

关键词：

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6467

简单数学题

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 308 Accepted Submission(s): 150

Problem Description

已知

F (n) = \sum i = 1 n (i \times \sum j = i n C i j)

Input

多组输入，每组输入占一行，包含一个整数n（1 <= n <= 1e18)。
数据不超过300000组。

Output

对于每组输入，输出一行，包括一个数代表答案。

Sample Input

5 100

Sample Output

129 660756544

Source

“字节跳动-文远知行杯”广东工业大学第十四届程序设计竞赛

解题思路：

技术图片

但是这道题只推出递推公式是不行的，因为普通的乘法运算会导致溢出。

但是log2的优化乘法又会超时，所以需要O(1)的优化乘法防止溢出：

inline long long multi(long long x,long long y)

    long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
    return tmp<0 ? tmp+mod : tmp;

AC code：

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 #define LL long long
 4 using namespace std;
 5 const LL mod = 1000000007;
 6 
 7 inline long long multi(long long x,long long y)
 8 
 9     long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
10     return tmp<0 ? tmp+mod : tmp;
11 
12 
13 
14 LL qpow(LL a, LL n)
15 
16     LL res = 1;
17     while(n)
18         if(n&1) res = multi(res, a)%mod;
19         a = multi(a, a);
20         n>>=1;
21     
22     return res%mod;
23 
24 
25 
26 int main()
27 
28 //    freopen("result.out", "w", stdout);
29     LL N, p, ans;
30     while(~scanf("%lld", &N))
31         p = qpow(2, N);
32         ans = (multi((N-1), p)%mod+1)%mod;
33         printf("%lld
", ans);
34     
35 
36     return 0;
37

2017"百度之星"程序设计大赛-复赛1003&&hdu6146pokémongo数学，递推，dp

PokémonGOTimeLimit:3000/1500MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):171 AcceptedSubmission(s):104ProblemDescription 查看详情

简单数学（组合数+求数列通项公式）(代码片段)

...目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6467看到这题，简单数学？？？对不起我给数学老师丢脸了！这里解释一下第二步到第三步：假设n=3，第二步1*C（1，1）+1*C（1，2）+1*C（1，3）+2*C（2，2）+2*C（2，3）+3*C（3，3），第三步1*C... 查看详情

hdu6533(贪心&递推)(代码片段)

HDU6533(贪心&递推)显然是对边排序，从小到大选，把图画一下，对每层进行递推，维护前一个层的sumsumsum，每次sum×nsum\\timesnsum×n，然后再加上当前层的边权即可。//Problem:B-BuildTree//Contest:VirtualJudge-2019CCPC... 查看详情

hdu2013（递推&递归_d题）解题报告

...个，给出第几天吃到只剩一个，求开始时的数量。思路：递推。按照每天的处理方式反向处理一下，最终得到结果。代码：查看详情

hdu2044（递推&递归_a题）解题报告

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2044------------------------------------------------------------------------------------题意：只能爬向+1或者+2的房间，求第a个房间到第b个房间的路线多少。思路：递归，爬向第k个房间只能从第k-1或者k-2... 查看详情

hdu4908&bestcoderround#3bestcodersequence（组合数学）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4908BestCoderSequenceTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):618 &nb 查看详情

hdu5379mahjongtree(树的遍历&组合数学)

本文纯属原创，转载请注明出处。谢谢。http://blog.csdn.net/zip_fan题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5379TimeLimit:6000/3000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)Problem 查看详情

2017多校第一套&&hdu6038思维数学

链接 http://acm.hdu.edu.cn/showproblem.php?pid=6038 题意：给你一个a序列，代表0到n-1的排列；一个b序列代表0到m-1的排列。问你可以找出多少种函数关系f，f的定义域内的i都满足f(i)=b[f(a[i])]; 分析：这个主要是找循环节循环... 查看详情

hdu2547无剑无我（数学）

#include<cstdio>#include<iostream>#include<cmath>intmain(){doublea,b,c,d,m;intt;scanf("%d",&t);while(t--){scanf("%lf%lf%lf%lf",&a,&b,&c,&d);m=sqrt((a-c)*(a-c)+(b- 查看详情

收藏推荐markdown常用latex数学符号&公式(代码片段)

...博客、写文档中经常需要编辑各种形式的数学公式。对于简单的公式，可以在word中编辑，对于复杂的公式一般以截图、粘贴的方式到网站上去自动识别生成公式（推荐:在线LaTeX公式编辑器）。利用Markdown中的LaTeX... 查看详情

使用latex插入数学公式(代码片段)

初级运算关系运算符希腊字母集合运算符逻辑运算符空格问题矩阵格式矩阵格式有三种：无括号的矩阵使用eginmatrix…endmatrix来生成矩阵，其中matrix是Latex的矩阵命令，矩阵命令中每一行以\\结束，矩阵的元素之间用&来分... 查看详情

hdu2193-avl-数据结构-avl

...水过。题目意思：题目大意：n个点的AVL树最多有几层。递推公式： a[i]=a[i-1]+a[i- 查看详情

hdu3232&&uva12230(简单期望)

CrossingRiversTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):738 AcceptedSubmission(s):387ProblemDescriptionYo 查看详情

hdu-2058thesumproblem（简单数学题）

题意：求出所有的情况，等差上去可以达到m值。原来想着暴力搜索，但是题中的数据太大，所以时间超限。百度了一下，发现可以套公式。等差求和公式:Sn=(a1+aN)*n/2 =(a1+a1+d(n-1))*n/2 =a1*n+d(n-1)*n/2;因为此处公差d=1... 查看详情

latex教程04.latex插入数学公式与符号(代码片段)

...章里用到的数学公式格式都放上来供大家参考学习首先最简单的数学模式$xxx$%一个$符号，中间的内容是行内模式$$xxx$$%两个$符号，中间的内容是行间模式(行间模式会单独占一行)更进一步就是带有公式编号的模式\\begineqna... 查看详情

hdu2070

ps:...递推..还是给出公式那种...代码:#include"stdio.h"#defineLLlonglongLLdp[55];intmain(){inti,n;dp[0]=0;dp[1]=1;for(i=2;i<55;i++)dp[i]=dp[i-1]+dp[i-2];while(~scanf("%d",&n)){if(n==-1)return0;printf("%lld 查看详情

hdu2050折线分割平面（递推公式）

折线分割平面TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):29965 AcceptedSubmission(s):20289ProblemDescription我们看到过很查看详情

hdu1030数学题

给出两点，求这两点在图上的最短路径分别以最上，左下，右下为顶点，看这个三角图形ans=这三种情况下两点的层数差#include"stdio.h"#include"string.h"#include"math.h"intmain(){intn,m,sn,sm,rn,rm,ln,lm,ans;while(scanf("%d%d",&n,&m)!=EOF){sn=sqrt(n);if... 查看详情

正文