题意 : 给出 N 个糖果、老师按顺序给 1~N 编号的学生分配糖果、每个学生要么不分、要么最少分一个、且由于是按顺序发放、那么对于某个有分到糖果的编号为 i 的学生、则 1~(i-1) 这些学生都最少有一个糖果、老师必须分完 N 个糖果、问你最后不同的分配方式有多少种
分析 :
队友根据组合计数的方法推出了答案是 2^(N-1)
你也可以通过打表的方式来找到这个规律
但是这里 N 很大、不能直接进行快速幂运算
需要进行降幂处理
有一个男人、他叫欧拉
提出了一个降幂公式
a^n mod c = a^( n % φ(c) + φ(c) ) mod c
条件是 n ≥ φ(c)
注 : φ(n) 是欧拉函数的意思、代表从 1 ~ n 与 n 互质的数的个数
当 n 为质数的时候 φ(n) = n-1
所以只要在输入的时候、将指数适当进行模运算处理、就可以通过快速幂通过此题
#include<bits/stdc++.h> #define LL long long #define ULL unsigned long long #define scl(i) scanf("%lld", &i) #define scll(i, j) scanf("%lld %lld", &i, &j) #define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k) #define scllll(i, j, k, l) scanf("%lld %lld %lld %lld", &i, &j, &k, &l) #define scs(i) scanf("%s", i) #define sci(i) scanf("%d", &i) #define scd(i) scanf("%lf", &i) #define scIl(i) scanf("%I64d", &i) #define scii(i, j) scanf("%d %d", &i, &j) #define scdd(i, j) scanf("%lf %lf", &i, &j) #define scIll(i, j) scanf("%I64d %I64d", &i, &j) #define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k) #define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k) #define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k) #define sciiii(i, j, k, l) scanf("%d %d %d %d", &i, &j, &k, &l) #define scdddd(i, j, k, l) scanf("%lf %lf %lf %lf", &i, &j, &k, &l) #define scIllll(i, j, k, l) scanf("%I64d %I64d %I64d %I64d", &i, &j, &k, &l) #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define lowbit(i) (i & (-i)) #define mem(i, j) memset(i, j, sizeof(i)) #define fir first #define sec second #define VI vector<int> #define ins(i) insert(i) #define pb(i) push_back(i) #define pii pair<int, int> #define VL vector<long long> #define mk(i, j) make_pair(i, j) #define all(i) i.begin(), i.end() #define pll pair<long long, long long> #define _TIME 0 #define _INPUT 0 #define _OUTPUT 0 clock_t START, END; void __stTIME(); void __enTIME(); void __IOPUT(); using namespace std; const int maxn = 1e6 + 10; const LL mod = 1e9 + 7; char str[maxn]; LL pow_mod(LL a, LL b) { a %= mod; LL ret = 1LL; while(b){ if(b & 1) ret = ret * a % mod; a = a * a % mod; b >>= 1; }return ret; } int main(void){__stTIME();__IOPUT(); int nCase; sci(nCase); while(nCase--){ scs(str); int len = strlen(str); LL Index = 0; for(int i=0; i<len; i++) Index = ((Index * 10) + (str[i]-'0'))%(mod-1); printf("%lld ", pow_mod(2LL, Index-1 < 0 ? 0 : Index-1)); } __enTIME();return 0;} void __stTIME() { #if _TIME START = clock(); #endif } void __enTIME() { #if _TIME END = clock(); cerr<<"execute time = "<<(double)(END-START)/CLOCKS_PER_SEC<<endl; #endif } void __IOPUT() { #if _INPUT freopen("in.txt", "r", stdin); #endif #if _OUTPUT freopen("out.txt", "w", stdout); #endif }