A-SUM(HDU 4704)

本文主要是介绍A-SUM(HDU 4704)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

VJ上的原题地址：https://cn.vjudge.net/contest/273543#problem/A

题目大意：给定一个数n，求把n分解为几个正整数的和的方法数，并且4=1+1+2和4=1+2+1是不同的

思路：

1.隔板法：把n看作n个小球，每个小球都是1，这样和仍为n，然后在n-1个空当之间放入木板，因为每个空当都有放与不放两种可能，所以一共的方法数为2^(n-1)

2.考虑到数据范围非常大，所以用string存储数据

3.模运算的加法法则：(a+b) mod c = (a mod c +b mod c) mod c

4.因为任何十进制正整数都可以写成当前数位的数*10^k (k>=0)的形式，例如：233=2*100+3*10+3*1 。所以，根据上一条性质，可以对大整数遍历一遍，每加到k上之前都模一下就能在保证同余的基础上保证k不越界

5.快速幂，这个不用我说了吧。。。

直接上代码：

#include<iostream>
#include<cstdio>
#include<string>using namespace std;const long long mod=1e9+7;
string s;long long qpow(long long a,long long b)
{long long ans=1;while(b>0){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}	return ans;
}
int main()
{long long k,len;while(cin>>s){k=0;len=s.size();for(int i=0;i<len;i++){k=(k*10+s[i]-'0')%(mod-1);}k=(k-1)%(mod-1);cout<<qpow(2,k)<<endl;}return 0;
}

 

这篇关于A-SUM(HDU 4704)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---