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

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

阅读量：6693 次

发布时间：2019-06-25

本文共 1340 字，大约阅读时间需要 4 分钟。

题意：给你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
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               typedef long long ll;const int maxn = 1e5 + 10;const int seed = 131;const ll MOD = 1e9 + 7;const ll MOD1 = 1e9 + 6;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[0] - '0'; int len = strlen(num); for(int i = 1; i < len - 1; i++) ans = (ans * 10 + num[i] - '0') % MOD1; if(len > 1) ans = ans * 10 + num[len - 1] - '0'; return (ans - 1) % MOD1;}ll pmul(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans = (ans * a) % MOD; a = a * a % MOD; b >>= 1; } return ans;}int main(){ int T; ll n, p; scanf("%d", &T); while(T--){ scanf("%s", num); p = getmod(); printf("%lld\n", pmul(2, p)); } return 0;}

转载于:https://www.cnblogs.com/KirinSB/p/9651627.html

你可能感兴趣的文章