hdu4740 Sum

题意：把一个数值为n的数字,可以把他分成 由 i个数相加的形式 1<=i<=n 问有一共有多少种分配方式 (1<=n<=1e100000)

    0. 读准题,当时被卡死了 :The input file consists of multiple test cases.
    1. 隔板定理：先把n分成n个数 组成的形式，那么每个数都是1 ,n个1之间有n-1个空,在选择由几个数组成的n的形式的时              候相当于在这 n-1个空之间插入隔板进行分开
            有 C(n-1,0)+C(n-1,1)+C(n-1,2)+C(n-1,3).....+C(n-1,n-1) = 2^(n-1)   (隔板定理) (C(n,0)+.....+C(n,n)=2^n)
    2. 1<=n<=1e100000 不降幂没法做. gcd(2,mod)=1 mod为素数
       费马小定理和欧拉降幂都行,当然是用费马小定理时间复杂度更优,不用计算欧拉函数值得因子来降幂了
       降幂原理: a^(n-1)=a^(k*(p-1)+r)而a^(k *(p-1))%p=1
    3. 一个知识点吧: 在对输入的n(灰常大)要mod p 进行处理的时候可以这样处理:
            n%p =((((((a1%p)*10+a2)%p)*10+a3)%p)*10+a4)%p  其中n=a1a2a3a4a5 都当ai当作字符来读入

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define X 10005 #define inf 0x3f3f3f3f #define PI 3.141592653589793238462643383 const int mod=1e9+7; const int N=1e7; ll Pow(ll a,ll n) {ll ans=1;while(n){if(n&1)ans=ans*a%mod;a=a*a%mod;n>>=1;}return ans%mod; } int main() {ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);string str;while(cin>>str){ll n=0;for(int i=0; str[i]!='\0'; ++i) n=(n*10+str[i]-'0')%(mod-1);n=n-1;ll ans=Pow(2,n);cout<<ans<<endl;}return 0;}

 

总结

以上是生活随笔为你收集整理的hdu4740 Sum的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。