题目描述:
给定一个整数 N, 有一个函数 S(x),S(x) 表示把整数 N 分成 x 份有多少个方法.
求 S(1)+S(2)+......+S(N) 的和.
分析: 可以把 N 看出 N 个小球 (把 N 看出 N 个 1 的和), 放入 x 个洞里面, 有多少种方法. 由插板法可以得到 S(x)=C(x-1,n-1).(x-1 在上, N-1 在下).
那么和就是 sum=S(1)+S(2)+......+S(N)=C(0,N-1)+C(1,N-1)+......+C(N-1,N-1)=2^(N-1). 答案就是求 2^(N-1).
因为 N 很大, 只能用字符串存起来. 首先把字符串代表的数减一, 直接把最后的数减 1 即可. 如果遇到最后的数为 0, 那么就要把这个数变为 9, 把前面的数减一. 比如 (10-1 变成 09).
我的想法就是把字符串拆成一位一位的. 比如求 2^(22) 可以拆成 2^(20) * 2^(2).2^(2) 很简单, 把他的基数 2 平方即可. 那 2^(20) 呢, 同样, 把基数变成 2^(10), 再把基数平方即可. 这样每一位的基数, 是他前一位的 10 次方, 每次保留基数, 就可以一步一步求. 再用快速幂运算即可.
题目有点误导的地方就他输入的数不止一个.
代码:
- #include <iostream>
- #include <algorithm>
- #include <cstdio>
- #include <string.h>
- using namespace std;
- typedef long long ll;
- const ll mod=1000000007;
- ll pow(ll x,int n)
- {
- if(n==0) return 1;
- if(n==1) return x%mod;
- ll res=1;
- while(n)
- {
- if(n&1) res=res*x%mod;
- x=x*x%mod;
- n>>=1;
- }
- return res;
- }
- int main()
- {
- char N[2000006];
- while(scanf("%s",N)!=EOF)
- {
- int len=strlen(N);
- ll base=2;
- ll ans=1;
- int tail=len-1;
- while(N[tail]=='0')
- {
- N[tail]='9';
- tail--;
- }
- N[tail]--;
- for(int i=len-1;i>=0;i--)
- {
- int num=N[i]-'0';
- ans=ans*pow(base,num)%mod;
- base=pow(base,10);
- }
- printf("%lld\n",ans%mod);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3400822.html