[2018 ACM-ICPC 焦作赛区网络赛] G - Give Candies（找规律+快速幂）

【文件属性】：
文件名称：[2018 ACM-ICPC 焦作赛区网络赛] G - Give Candies（找规律+快速幂）
文件大小：812B
文件格式：CPP
更新时间：2022-05-08 11:12:54
ACM 题意：有一位老师给N个学生分N个糖果，老师从第一个学生开始发糖果，老师所经过的学生至少要被分到一个糖果，求有多少种分法，比如这里有三个学生，老师有三个糖果，有四种分法：{3，0，0}， {2，1，0}，{1，2，0}，{1，1，1}。 思路：这个题和HDU - 5703类似，其实就是拆数问题，一个数的拆法其实就是2^(N-1)，具体证明过程可以直接搜刚才杭电那道题的题解，所以这道题其实就是让你算2^(N-1)，但是题目给的N特别大， 可以达到10^100000，我们只能用字符串读这个数，这样的话我们肯定不能直接用快速幂算，其实有一个性质，2^N模一个质数，它的结果是具有周期性的，周期长度为mod-1，这道题就利用这个周期 性，具体步骤就是：先把N转化成模mod-1下的的数，然后用这个数计算快速幂，得到的结果是和原数相同的。