题目描述
平平在公园里游玩时捡到了很多小球，而且每个球都不一样。平平找遍了全身只发现了3个一模一样的袋子。他打算把这些小球都装进袋子里（袋子可以为空）。他想知道他总共有多少种放法。
将N个不同的球放到3个相同的袋子里，求放球的方案总数M。
结果可能很大，我们仅要求输出M mod K的结果。
现在，平平已经统计出了N<=10的所有情况。见下表：
输入
两个整数N,K，N表示球的个数。
输出
输出仅包括一行，一个整数M mod K 。
样例输入
11 10000
样例输出
9525
提示
对于 40%数据,10<=N<=10,000
对于100%数据,10<=N<=1,000,000,000
对于 100%数据，K<=100,000
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
根据题目的意思进行思考，就会发现这个题和组合数学有几分关系，再看数据范围就知道肯定是快速幂
剩下的就是推式子根据上面的已经给出的数据来看可以推出a[n]=a[n-1]*3-1；找到规律之后，推出式子ans=(3n-1+1)/2;
但是注意最后的时候还要除以2，所以取模的时候要对模数的2倍进行取模
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma comment(linker, "/stack:200000000") #pragma GCC optimize (2) #pragma G++ optimize (2) #include <bits/stdc++.h> #include <algorithm> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define wuyt main typedef long long ll; #define HEAP(...) priority_queue<__VA_ARGS__ > #define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > template<class T> inline T min(T &x,const T &y){return x>y?y:x;} template<class T> inline T max(T &x,const T &y){return x<y?y:x;} //#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) //char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const ll inf = 1e15; const int maxn = 2e5 + 7; const int mod = 1e9 + 7; #define start int wuyt() #define end return 0 ll n,ans,k,e[maxn]; ll superpow(ll a,ll b,ll c){ ll ans=1; ll temp=a; while(b){ if(b&1) ans=(ans*temp)%c; temp=(temp*temp)%c; b>>=1; } return ans; } start{ n=read,k=read; printf("%lld\n",(superpow(3,n-1,k<<1)+1)>>1); end; }
