题目:http://acm.hdu.edu.cn/showproblem.php?pid=4704
题目大意:整数划分,问你一个整数能划分成几种组合。
思路:答案就是 2^(n - 1),然后n很大,都高精了。然后就是找规律,去找循环节,一个 for 下去,发现 2^500000003 = 1 = 2^0,所以就是n = (n - 1) % 500000003, - 1之后再处理,n是高精,就先用字符串存出来,因为m[ i ] = (m[ i - 1 ]*10 + str[ i ] - ' 0 ' )%mod,就是一遍扫过去就好了。
先开始高精那里不会取模,囧。。
其实这道题目用的是费马小定理:
a^(p-1)≡1(mod p)
所以 2^(n - 1) = 2^((n-1)%(mod -1))%mod;
只需要将下面代码里的 500000003 改为 (mod - 1)就好,正好两倍 。。。= =
代码如下:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef __int64 lld; const int MOD = 1e9 + 7; char str[111111]; lld quick_mod(lld k) { lld ans = 1; lld a = 2; while(k) { if(k&1) ans = (ans*a)%MOD; a = (a*a)%MOD; k >>= 1; } return ans; } int main() { while(~scanf("%s",str)) { int len = strlen(str); lld k = 0; for(int i = 0;i<len;i++) k = (k*10 + str[i] - '0')%500000003; k = (k -1 + 500000003)%500000003; printf("%I64d\n",quick_mod(k)); } return 0; } /* 500000003 */