Fly to sky, chase my dream!
区间DP小结(附经典例题)
——这篇文章主要想总结下区间DP的经典题目，同时给自己复习巩固这方面知识点。
区间DP，顾名思义是在区间上DP，它的主要思想就是先在小区间进行DP得到最优解，然后再利用小区间的最优解合并求大区间的最优解。
二、实现思路
下面给出区间DP最简单形式的伪代码(具体要根据题目修改)
//mst(dp,0) 初始化DP数组
for(int i=1;i&=n;i++)
dp[i][i]=初始值
for(int len=2;len&=n;len++)
//区间长度
for(int i=1;i&=n;i++)
//枚举起点
int j=i+len-1;
//区间终点
//越界结束
for(int k=i;k&j;k++)
//枚举分割点，构造状态转移方程
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
三、经典例题
1. 石子合并问题
石子合并（一）
时间限制： ms
内存限制：65535 KB
有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。
有多组测试数据，输入到文件结束。每组测试数据第一行有一个整数n，表示有n堆石子。
接下来的一行有n（0& n &200）个数，分别表示这n堆石子的数目，用空格隔开
输出总代价的最小值，占单独的一行
13 7 8 16 21 4 18
我们dp[i][j]来表示合并第i堆到第j堆石子的最小代价。
那么状态转移方程为
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
其中w[i][j]表示把两部分合并起来的代价，即从第i堆到第j堆石子个数的和，为了方便查询，我们可以用sum[i]表示从第1堆到第i堆的石子个数和，那么w[i][j]=sum[j]-sum[i-1].
#include &cstdio&
#include &queue&
#include &cstring&
#include &algorithm&
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
const int maxn = 205;
const ll mod = 1e9+7;
const ll INF = 1e18;
const double eps = 1e-9;
int sum[maxn];
int dp[maxn][maxn];
int main()
while(~scanf("%d",&n))
mst(dp,0x3f);
for(int i=1;i&=n;i++)
scanf("%d",&x);
sum[i]=sum[i-1]+x;
dp[i][i]=0;
for(int len=2;len&=n;len++)
for(int i=1;i&=n;i++)
int j=i+len-1;
for(int k=i;k&j;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
printf("%d\n",dp[1][n]);
【平行四边形优化】
上面的代码运行时间在240ms左右，通过这题完全没问题，但我们还可以考虑优化。
由于状态转移时是三重循环的，我们想能否把其中一层优化呢？尤其是枚举分割点的那个，显然我们用了大量的时间去寻找这个最优分割点，所以我们考虑把这个点找到后保存下来
用s[i][j]表示区间[i,j]中的最优分割点，那么第三重循环可以从[i,j-1)优化到【s[i][j-1],s[i+1][j]】。(这个时候小区间s[i][j-1]和s[i+1][j]的值已经求出来了，然后通过这个循环又可以得到s[i][j]的值)。
关于平行四边形优化的证明可以参考这篇博客:
#include &cstdio&
#include &queue&
#include &cstring&
#include &algorithm&
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
const int maxn = 205;
const ll mod = 1e9+7;
const ll INF = 1e18;
const double eps = 1e-9;
int sum[maxn];
int dp[maxn][maxn];
int s[maxn][maxn];
int main()
while(~scanf("%d",&n))
mst(dp,0x3f);
for(int i=1;i&=n;i++)
scanf("%d",&x);
sum[i]=sum[i-1]+x;
dp[i][i]=0;
s[i][i]=i;
for(int len=2;len&=n;len++)
for(int i=1;i&=n;i++)
int j=i+len-1;
for(int k=s[i][j-1];k&=s[i+1][j];k++)
if(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]&dp[i][j])
dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
s[i][j]=k;
printf("%d\n",dp[1][n]);
附：此题的升级版
Monkey Party
Time Limit:
MS (Java/Others)
Memory Limit:36 K (Java/Others)
Total Submission(s): 1738
Accepted Submission(s): 784
Problem Description
Far away from our world, there is a banana forest. And many lovely monkeys livethere. One day, SDH(Song Da Hou), who is the king of banana forest, decides tohold a big party to celebrate Crazy Bananas Day. But the little monkeys
don'tknow each other, so as the king, SDH must do something.
Now there are n monkeys sitting in a circle, and each monkey has a makingfriends time. Also, each monkey has two neighbor. SDH wants to introduce themto each other, and the rules are:
1.every time, he can only introduce one monkey and one of this monkey'sneighbor.
2.if he introduce A and B, then every monkey A already knows will know everymonkey B already knows, and the total time for this introducing is the sum ofthe making friends time of all the monkeys A and B
3.each little
In order to begin the party and eat bananas as soon as possible, SDH want toknow the mininal time he needs on introducing.
There is several test cases. In each case, the first line is n(1 ≤ n ≤ 1000), whichis the number of monkeys. The next line contains n positive integers(less than1000), means the making friends time(in order, the first one and
the last oneare neighbors). The input is end of file.
For each case, you should print a line giving the mininal time SDH needs on introducing.
Sample Input
5 2 4 7 6 1 3 9
Sample Output
问题转化后其实就是环形石子合并，即现在有围成一圈的若干堆石子，其他条件跟其那面那题相同，问合并所需最小代价。
我们需要做的是尽量向简单的问题转化，可以把前n-1堆石子一个个移到第n个后面，那样环就变成了线，即现在有2*n-1堆石子需要合并，我们只要求下面的式子即可。求法与上面那题完全一样。
#include &cstdio&
#include &string&
#include &cstring&
#include &algorithm&
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
const int maxn = 1005*2;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;
int a[maxn];
int sum[maxn];
int dp[maxn][maxn];
int s[maxn][maxn];
int main()
while(~scanf("%d",&n))
mst(dp,0x3f);
for(int i=1;i&=n;i++)
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
s[i][i]=i;
dp[i][i]=0;
for(int i=1;i&n;i++)
sum[i+n]=sum[i+n-1]+a[i];
s[i+n][i+n]=i+n;
dp[i+n][i+n]=0;
for(int len=2;len&=n;len++)
for(int i=1;i&=2*n-1;i++)
int j=i+len-1;
if(j&2*n-1)
for(int k=s[i][j-1];k&=s[i+1][j];k++)
if(dp[i][j]&dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])
dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
s[i][j]=k;
int ans=INF;
for(int i=1;i&=n;i++)
ans=min(ans,dp[i][i+n-1]);
printf("%d\n",ans);
2. 括号匹配问题
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 8710
Accepted: 4659
Description
We give the following inductive definition of a “regular brackets” sequence:
the empty sequence is a regular brackets sequence,if s is a regular brackets sequence, then (s)
and [s] are regular brackets sequences, andif a andb are regular brackets sequences,
thenab is a regular brackets sequence.no other sequence is a regular brackets sequenceFor instance,all of the following character sequences are regular brackets sequences:
(), [], (()), ()[], ()[()]
while thefollowing character sequences are not:
(, ], )(, ([)], ([(]
Given a brackets sequence of characters a1a2
… an,your goal is to find the length of the longest regular brackets sequence that is a subsequence ofs.
That is, you wish to find the largestmsuch that for indicesi1,i2,
…,imwhere 1 ≤i1
&i2 & … &im≤n,ai1ai2
… aim is a regular bracketssequence.
Given the initial sequence ([([]])], the longest regularbrackets subsequence is[([])].
The input test file will contain multiple test cases. Each input test case consists of asingle line containing only the characters(,),[,
and]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and
should not be processed.
For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.
Sample Input
Sample Output
给出一个的只有'(',')','[',']'四种括号组成的字符串，求最多有多少个括号满足题目里所描述的完全匹配。
用dp[i][j]表示区间[i,j]里最大完全匹配数。
只要得到了dp[i][j]，那么就可以得到dp[i-1][j+1]
dp[i-1][j+1]=dp[i][j]+(s[i-1]与[j+1]匹配 ? 2 : 0)
然后利用状态转移方程更新一下区间最优解即可。
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j])
#include &cstdio&
#include &queue&
#include &cstring&
#include &algorithm&
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
const int maxn = 105;
const ll mod = 1e9+7;
const ll INF = 1e18;
const double eps = 1e-9;
char s[maxn];
int dp[maxn][maxn];
int main()
while(~scanf("%s",s+1)&&s[1]!='e')
int n=strlen(s+1);
mst(dp,0);
for(int len=2;len&=n;len++)
for(int i=1;i&=n;i++)
int j=i+len-1;
if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']')
dp[i][j]=dp[i+1][j-1]+2;
for(int k=i;k&j;k++)
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]);
printf("%d\n",dp[1][n]);
括号匹配（二）
时间限制：1000 ms
内存限制：65535 KB
给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的
第一行输入一个正整数N，表示测试数据组数(N&=10)
每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100
对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行
上一题求的是满足完美匹配的最大括号数量，而这题问的是使所有括号完美匹配需要添加的最小括号数量
显然，要使添加的括号尽量少，我们需要使原来的括号序列尽可能多得匹配，即先求最大匹配数量(跟上题一样)，那么还剩下一些没有匹配的括号，我们就需要依次加上一个括号使它们得到匹配。综上所述，所求=原序列括号数量-最大匹配括号数量。(因此此题的代码与上题几乎一致)。
#include &cstdio&
#include &queue&
#include &cstring&
#include &algorithm&
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
const int maxn = 105;
const ll mod = 1e9+7;
const ll INF = 1e18;
const double eps = 1e-9;
char s[maxn];
int dp[maxn][maxn];
int main()
scanf("%s",s+1);
int n=strlen(s+1);
mst(dp,0);
for(int len=2;len&=n;len++)
for(int i=1;i&=n;i++)
int j=i+len-1;
if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']')
dp[i][j]=dp[i+1][j-1]+2;
for(int k=i;k&j;k++)
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]);
printf("%d\n",n-dp[1][n]);
3. 整数划分问题
整数划分（四）
时间限制：1000 ms
内存限制：65535 KB
暑假来了，hrdv又要留学校在参加ACM集训了，集训的生活非常Happy（ps：你懂得），可是他最近遇到了一个难题，让他百思不得其解，他非常郁闷。。亲爱的你能帮帮他吗？
问题是我们经常见到的整数划分，给出两个整数 n , m ,要求在 n 中加入m - 1 个乘号，将n分成m段，求出这m段的最大乘积
第一行是一个整数T，表示有T组测试数据
接下来T行，每行有两个正整数 n，m ( 1&= n & 10^19, 0 & m &= n的位数)；
输出每组测试样例结果为一个整数占一行
给出一个数n,要求在n的数位间插入(m-1)个乘号，将n分成了m段，求这m段的最大乘积。
用dp[i][j]表示从第一位到第i位共插入j个乘号后乘积的最大值。根据区间DP的思想我们可以从插入较少乘号的结果算出插入较多乘号的结果。
方法是当我们要放第j的乘号时枚举放的位置。
状态转移方程为
dp[i][j]=max(dp[i][j],dp[k][j-1]*num[k+1][i])
其中num[i][j]表示从s[i]到s[j]这段连续区间代表的数值。
#include &cstdio&
#include &queue&
#include &cstring&
#include &algorithm&
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
const int maxn = 25;
const ll mod = 1e9+7;
const ll INF = 1e18;
const double eps = 1e-9;
char s[maxn];
ll dp[maxn][maxn];
ll num[maxn][maxn];
int main()
scanf("%s%d",s+1,&m);
mst(dp,0);
int len=strlen(s+1);
for(int i=1;i&=i++)
num[i][i]=s[i]-'0';
for(int j=i+1;j&=j++)
num[i][j]=num[i][j-1]*10+s[j]-'0';
for(int i=1;i&=i++)
dp[i][0]=num[1][i];
for(int j=1;j&m;j++)
for(int i=j+1;i&=i++)
for(int k=j;k&i;k++)
dp[i][j]=max(dp[i][j],dp[k][j-1]*num[k+1][i]);
printf("%lld\n",dp[len][m-1]);
凸多边形三角划分问题
Problem Description
给定一个具有N(N&=50)个顶点(从1到N编号)的凸多边形，每个顶点的权值已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权值的乘积之和最小。
第一行为顶点数N，第二行为N个顶点（从1到N）的权值。
乘积之和的最小值。题目保证结果在int范围内。
Sample Input
121 122 123 245 231
Sample Output
给出一个数n,要求在n的数位间插入(m-1)个乘号，将n分成了m段，求这m段的最大乘积。
用dp[i,j]表示从顶点i到顶点j的凸多边形三角剖分后所得到的最大乘积。
那么可以写出状态转移方程，并通过枚举分割点来转移。
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);
#include &cstdio&
#include &queue&
#include &cstring&
#include &algorithm&
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
const int maxn = 55;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;
int a[maxn];
int dp[maxn][maxn];
int main()
while(~scanf("%d",&n))
for(int i=1;i&=n;i++)
scanf("%d",&a[i]);
mst(dp,0);
for(int len=3;len&=n;len++)
for(int i=1;i&=n;i++)
int j=i+len-1;
dp[i][j]=INF;
for(int k=i+1;k&j;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);
printf("%d\n",dp[1][n]);
四、拓展例题
1. HDOJ 2513 Cake slicing
Cake slicing
Time Limit:
MS (Java/Others)
Memory Limit: K (Java/Others)
Total Submission(s): 283
Accepted Submission(s): 139
Problem Description
A rectangular cake with a grid of m*n unit squares on its top needs to be slicedinto pieces. Several cherries are scattered on the top of the cake with at mostone cherry on a unit square. The slicing should follow the rules below:
each piece is r
each cutting edge is straight a
each piece has o
each cut must split the cake you currently cut two separate parts
For example, assume that the cake has a grid of 3*4 unit squares on its top,and there are three cherries on the top, as shown in the figure below.
One allowable slicing is as follows.
For this way of slicing , the total length of the cutting edges is 2+4=6.
Another way of slicing is
In this case, the total length of the cutting edges is 3+2=5.
Give the shape of the cake and the scatter of the cherries , you are supposedto find
out the least total length of the cutting edges.
The input file contains multiple test cases. For each test case:
The first line contains three integers , n, m and k (1≤n, m≤20), where n*m isthe size of the unit square with a cherry on it . The two integers showrespectively the row number and the column number of the unit square in thegrid .
All integers in each line should be separated by blanks.
Output an integer indicating the least total length of the cutting edges.
Sample Input
Sample Output
有一个n*m大小的蛋糕，上面有k个樱桃，现在我们需要把这个蛋糕切成k份，使每份蛋糕上有一个樱桃，问最小切割长度和。(切割一刀必须切到底)
用dp[i][j][k][l]表示以(i,j)为左上角，(k,l)为右下角的矩形切成每份一个樱桃的最小切割长度。然后就利用区间DP的作用，枚举切割点，从小区间转移到大区间。由于这道题不同区间樱桃个数不同，故用递归的写法会方便些。
#include &cstdio&
#include &cmath&
#include &queue&
#include &cstring&
#include &algorithm&
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
const int maxn = 25;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;
int n,m,k;
int dp[maxn][maxn][maxn][maxn];
bool flag[maxn][maxn];
//记录某个点是否有樱桃
int fun(int a,int b,int c,int d)
if(dp[a][b][c][d]!=-1)
//已经计算过
return dp[a][b][c][d];
int cnt=0;
for(int i=a;i&=c;i++)
for(int j=b;j&=d;j++)
if(flag[i][j])
if(cnt&=1)
//区域内樱桃个数小于2，那么不用切割
return dp[a][b][c][d]=0;
int Min=INF;
for(int i=a;i&c;i++)
Min=min(Min,fun(a,b,i,d)+fun(i+1,b,c,d)+(d-b+1));
for(int i=b;i&d;i++)
Min=min(Min,fun(a,b,c,i)+fun(a,i+1,c,d)+(c-a+1));
return dp[a][b][c][d]=M
int main()
int cas=1;
while(~scanf("%d%d%d",&n,&m,&k))
mst(dp,-1);
mst(flag,0);
for(int i=0;i&k;i++)
scanf("%d%d",&x,&y);
flag[x][y]=1;
int ans=fun(1,1,n,m);
printf("Case %d: %d\n",cas++,ans);
HDOJ 2476 String painter
String painter
Time Limit:
MS (Java/Others)
Memory Limit: K (Java/Others)
Total Submission(s): 4691
Accepted Submission(s): 2208
Problem Description
There are two strings A and B with equal length. Both strings are made up of lowercase letters. Now you have a powerful string painter. With the help of thepainter, you can change a segment of characters of a string to any othercharacter
you want. That is, after using the painter, the segment is made up ofonly one kind of character. Now your task is to change A to B using stringpainter. What’s the minimum number of operations?
Input contains multiple cases. Each case consists of two lines:
The first line contains string A.
The second line contains string B.
The length of both strings will not be greater than 100.
A single line contains one integer representing the answer.
Sample Input
zzzzzfzzzzz
abcdefedcba
abababababab
cdcdcdcdcdcd
Sample Output
给出字符串A和B，每一次我们可以使用一种颜色（用字母代替）刷任意一个连续子序列，问将字符串A变成字符串B最少需要刷多少次。
分析了很久，发现直接去考虑将A串刷成B串非常困难。于是我们考虑间接转化。
用dp[i][j]表示把将一个空白串[i,j]刷成B字符串对应位置的最小次数。
用ans[i]表示把A串的区间[1,i]刷成B串需要的最小次数。
然后状态转移一下就OK啦。
#include &cstdio&
#include &cmath&
#include &queue&
#include &cstring&
#include &algorithm&
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
const int maxn = 105;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;
char s1[maxn],s2[maxn];
int dp[maxn][maxn];
int ans[maxn];
int main()
while(~scanf("%s%s",s1+1,s2+1))
int n=strlen(s1+1);
mst(dp,0);
for(int i=1;i&=n;i++)
for(int j=i;j&=n;j++)
dp[i][j]=j-i+1;
for(int j=1;j&=n;j++)
for(int i=j;i&=1;i--)
dp[i][j]=dp[i+1][j]+1;
for(int k=i+1;k&=j;k++)
if(s2[i]==s2[k])
//这样的话s2[i]可以跟左半区间一起刷到
dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
for(int i=1;i&=n;i++)
ans[i]=dp[1][i];
if(s1[i]==s2[i])
ans[i]=min(ans[i],ans[i-1]);
for(int j=1;j&i;j++)
ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
//已得出的最优解+剩下的按空白串去刷
printf("%d\n",ans[n]);
没有更多推荐了，POJ - 3264 Balanced Lineup ( RMQ
一直没学RMQ， 就是个dp区间维护问题，很好理解QWQ
求区间内最大值减最小值的大小
#include &iostream&
#include &algorithm&
using namespace std;
const int MAXN = 5e4+10;
int dp[MAXN][20], dp1[MAXN][20];
int mm[MAXN];
void init() {
for(int i = 0; i &= ++i)
mm[i] = i==0 ? -1 : mm[i&&1]+1;
for(int j = 1; j & 20; ++j) {
for(int i = 1; i+(1&&j)-1&=n; ++i) {
dp[i][j] = min(dp[i][j-1], dp[i+(1&&j-1)][j-1]);
for(int j = 1; j & 20; ++j) {
for(int i = 1; i+(1&&j)-1&=n; ++i) {
dp1[i][j] = max(dp1[i][j-1], dp1[i+(1&&j-1)][j-1]);
int main() {
ios::sync_with_stdio(false);
while(cin && n && q) {
for(int i = 1; i &= ++ i) {
dp[i][0] =
dp1[i][0] =
while(q--) {
cin && l &&
int k = mm[r-l+1];
cout && max(dp1[l][k], dp1[r-(1&&k)+1][k])-min(dp[l][k], dp[r-(1&&k)+1][k]) &&
没有更多推荐了，沉思了太久，那片刻，恍惚成了哲学家。
hdu 4704 Sum （整数和分解+快速幂+费马小定理降幂）
给n（1&n&）,求(s1+s2+s3+...+sn)mod(1e9+7)。其中si表示n由i个数相加而成的种数,如n=4,则s1=1,s2=3。
（全题文末）
整数n有种和分解方法。
费马小定理：p是质数，若p不能整除a，则 a^(p-1) ≡1（mod p）。可利用费马小定理降素数幂。
当m为素数，（m必须是素数才能用费马小定理）
a=2时。（a=2只是题中条件，a可以为其他值）
//==1为费马小定理的应用
例如，设p=7, n=32, 求2^32≡x(mod p)的值
由于p是素数，所以一定存在2^6≡1(mod p)
2^32%p=(2^[(6*5)+2])%p
=[2^(6*5)*2^2]%p
=[(2^(6*5)%p)*(2^2%p)]%p
//(a*b)%m=[(a%m)*(b%m)]%m;
=[1*(2^2%p)]%p
//2^(6*5)%p为对费马小定理的应用
题目相当于求n的分解种数。例如,n=x1+x2+x3+..xk是一种分解，把xi看成由xi个1组成，同理n即为n个1组成。
题目也就是给n个1分组的方法数（这不是类似于组合数学的小球间隔板问题吗）。每两个1之间是否放隔板，有放和不放两种选择，一共n-1个可选择间隔。so 总方法数为 。
由于n太大，不好处理啊。
指数太大，发现m=1e9+7为素数，则可用费马小定理(a^(p-1))≡1(mod p))降幂。
#include&iostream&
#include&cstdio&
#include&cstring&
typedef long long LL;
const int mod=1e9+7,N=1e5+5;
char a[N];
LL quick_mod(LL a,LL p)
//快速幂 (快速幂利用了二分思想和秦九昭算法)
ans=ans*a%
int main()
while(~scanf("%s",a))
int len=strlen(a);
for(int i=0;i&i++)
ans=(ans*10+a[i]-'0')%(mod-1);
ans=(ans-1+mod-1)%(mod-1);
printf("%lld\n",quick_mod(2,ans));
这道题还可以找循环结。
发现 2^ = 1 = 2^0，所以n=(n-1)%，所以 2^(n - 1) = 2^((n-1)%(mod -1))% （mod-1=）
Time Limit:1000MS
Memory Limit:131072KB
64bit IO Format:%I64d & %I64u
Description
Sample Input
Sample Output
1. For N = 2, S(1) = S(2) = 1. 2. The input file consists of multiple test cases.
没有更多推荐了，在这世界留下点什么
2016年12月
确定要删除当前文章？雷速体育发帖软件开发QQ
欢迎加入我们，一同切磋技术 &
用户名： &&&
密　码： &
共有 771 人关注过本帖
标题：【新手交流】取余数问题：输入x,n,输出x的n次方除1e9+7的余数[已有答案，欢 ...
来　自：223-3
等　级：新手上路
帖　子：14
结帖率：100%
&&问题点数：0&&回复次数：5&&&
【新手交流】取余数问题：输入x,n,输出x的n次方除1e9+7的余数[已有答案，欢迎讨论]
题目：输入x,n，范围（x&1000,n&1e18）输出x的n次方除1e9+7的余数
x,n很大的时候也要能输出答案 注意效率
#include&iostream&
int main()
&&& int x,n,i,
&&& cin&&x;
&&& cin&&n;
&&& ans=x%K;
&&& for (i=0;i&n-1 ;i++ )
&&&&&&&&ans=(ans*x)%K;
&&& cout&&
&&& return 0;
等　级：黑侠
帖　子：112
专家分：510
n是int型，恐怕会溢出
来　自：长长久久
等　级：版主
威　望：45
帖　子：4902
专家分：13909
记得处理长整形数据后可以用二分法或者理解成二进制的01位运算实现~
((a∧b)∧2)%c=(((a∧b)%c)∧2)%c
这个是我自己理解的~或者网上可以搜到这个思想的解法~记得是快速求余的方法么……一时不知道那个术语怎么表达了~
[此贴子已经被作者于 23:45编辑过]
[code]/*~个性签名:弟弟的妹妹叫妹妹,弟弟的姐姐叫姐姐~ 更~*/[/code]
来　自：长长久久
等　级：版主
威　望：45
帖　子：4902
专家分：13909
深夜断网……于是用手机临时用C敲一个……对着电脑测试了一下~看看有没有问题~
程序代码：
#include&stdio.h&
unsigned int&&fun(unsigned int x,unsigned int n,unsigned int k);
int main()
&&& unsigned int x=<font color=#;
&&& unsigned int n=<font color=#;
&&& unsigned int k=<font color=#;
&&& scanf(&%u%u%u&,&x,&n,&k);
&&& printf(&%u\n&,fun(x,n,k));
&&& return <font color=#;
unsigned int&&fun(unsigned int x,unsigned int n,unsigned int k)
&&& unsigned int s=<font color=#;
&&& unsigned int t=x%k;
&&& while (n)
&&&&&&&&&if (n%<font color=#)
&&&&&&&&&&&& s=s*t%k;
&&&&&&&&t=t*t%k;
&&&&&&&&n&&=<font color=#;
&&& return
[此贴子已经被作者于 03:17编辑过]
[code]/*~个性签名:弟弟的妹妹叫妹妹,弟弟的姐姐叫姐姐~ 更~*/[/code]
等　级：版主
威　望：248
帖　子：5612
专家分：31729
先分析一下
如果是依次相乘，因为结果是除的余数，那么中间结果最大可能出现
* 999，需要40bits存储
如果是用快速幂，因为结果是除的余数，那么中间结果最大可能出现
* ，需要60bits存储
所以这题的数据类型得用 uint64_t/int64_t
另外，既然题目中提到“余数”，那就不考虑x为负或n为负的情况。
程序代码：#include &stdio.h&
#include &inttypes.h&
int main(void)
&&& uint32_t x,
&&& scanf( &%&SCNu32&%&SCNu32, &x, &n );
&&& uint32_t r = <font color=#;
&&& for( uint64_t t=x; n!=<font color=#; n&&=<font color=#, t=t*t%K )
&&&&&&&&if( n%<font color=# == <font color=# )
&&&&&&&&&&&&r = (r*t)%K;
&&& printf( &%&PRIu32&\n&, r );
&&& return <font color=#;
收到的鲜花
附言：厉害~学习了~
来　自：223-3
等　级：新手上路
帖　子：14
这个是好久远的题了哈哈，蟹蟹大家帮助呀。当时只是想了最简单的方法，没有深入了解，回来之后发现大家的思路都很棒，十分感谢十分感谢~~~
版权所有，并保留所有权利。
Powered by , Processed in 0.049819 second(s), 9 queries.
Copyright&, BCCN.NET, All Rights Reserved