ACM-ICPC 2018 焦作赛区网络预赛G Give Candies（隔板定理 + 小费马定理 + 大数取模，组合数求和）题解

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：给你n个东西，叫你把n分成任意段，这样的分法有几种（例如3:1 1 1，1 2，2 1，3 ；所以3共有4种），n最多有1e5位，答案取模p = 1e9+7

思路：就是往n个东西中间插任意个板子，所以最多能插n - 1个，所以答案为2^(n - 1) % p。但是n最大有1e5位数，所以要用小费马定理化简。

小费马定理：假如p是质数，且gcd(a,p)=1，那么a ⁽ ^p ^- ¹ ⁾ ≡1（mod p）

所以我们只要把n - 1分解为n - 1 = k(p - 1) + m，而2^ k(p - 1) % p ≡1，所以2^(n - 1) % p = 2^m % p，化简完成。

所以我们把n - 1对p-1取模，用了大数取模

代码：

#include<queue>

#include<cstring>

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<vector>

#include<cstdio>

#include<iostream>

#include<algorithm>

typedef long long ll;

const int maxn = 1e5 + ;

const int seed = ;

const ll MOD = 1e9 + ;

const ll MOD1 = 1e9 + ;

const int INF = 0x3f3f3f3f;

using namespace std;

char num[maxn];

/*ll getmod(){

    ll ans = num[0] - '0';

    int len = strlen(num);

    for(int i = 1; i < len; i++)

        ans = (ans * 10 + num[i] - '0') % MOD1;

    return ans - 1;

}*/

ll getmod(){

    ll ans = num[] - '';

    int len = strlen(num);

    for(int i = ; i < len - ; i++)

        ans = (ans *  + num[i] - '') % MOD1;

    if(len > ) ans = ans *  + num[len - ] - '';

    return (ans - ) % MOD1;

}

ll pmul(ll a, ll b){

    ll ans = ;

    while(b){

        if(b & ) ans = (ans * a) % MOD;

        a = a * a % MOD;

        b >>= ;

    }

    return ans;

}

int main(){

    int T;

    ll n, p;

    scanf("%d", &T);

    while(T--){

        scanf("%s", num);

        p = getmod();

        printf("%lld\n", pmul(, p));

    }

    return ;

}