网站建设开票项目是什么,无极兼职网,网站建设许可证,新安网站开发题干#xff1a;
Eddy是个ACMer,他不仅喜欢做ACM题,而且对于Ranklist中每个人的ac数量也有一定的研究,他在无聊时经常在纸上把Ranklist上每个人的ac题目的数量摘录下来#xff0c;然后从中选择一部分人(或者全部)按照ac的数量分成两组进行比较#xff0c;他想使第一组中的最…题干
Eddy是个ACMer,他不仅喜欢做ACM题,而且对于Ranklist中每个人的ac数量也有一定的研究,他在无聊时经常在纸上把Ranklist上每个人的ac题目的数量摘录下来然后从中选择一部分人(或者全部)按照ac的数量分成两组进行比较他想使第一组中的最小ac数大于第二组中的最大ac数但是这样的情况会有很多聪明的你知道这样的情况有多少种吗? 特别说明为了问题的简化我们这里假设摘录下的人数为n人而且每个人ac的数量不会相等最后结果在64位整数范围内.
Input
输入包含多组数据每组包含一个整数n,表示从Ranklist上摘录的总人数。
Output
对于每个实例输出符合要求的总的方案数每个输出占一行。
Sample Input
2
4
Sample Output
1
17
解题报告 因为数字各不相同我们假设就是1~n。枚举每一个数计算以他作为右区间的最小值时产生的贡献。根据x个元素的集合的子集个数为2^x非空子集的个数为 (2^x - 1) 不难得到递推方程、、打表即可。因为题目说了数据不超longlong而打表后发现到60的时候已经溢出了所以只需要打表到60即可。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
ll dp[505];
ll qpow(ll a,ll k) {ll res 1;while(k) {if(k1) res * a;k1;a*a;}return res;
}
int main()
{dp[1] dp[0] 0;dp[2] 1;for(int i 3; i60; i) {for(int j 1; ji; j) {dp[i] qpow(2,j-1) * (qpow(2,i-j)-1);}}int n;while(~scanf(%d,n)) {printf(%lld\n,dp[n]);}return 0 ;}
