题目

https://www.rqnoj.cn/problem/85

题目描述
背景
平平在公园里游玩时捡到了很多小球，而且每个球都不一样。平平找遍了全身只发现了3个一模一样的袋子。他打算把这些小球都装进袋子里（袋子可以为空）。他想知道他总共有多少种放法。
题目描述
将N个不同的球放到3个相同的袋子里，求放球的方案总数M。
结果可能很大，我们仅要求输出M mod K的结果。
现在，平平已经统计出了N<=10的所有情况。见下表：
N 1 2 3 4 5 6 7 8 9 10
M 1 2 5 14 41 122 365 1094 3281 9842
数据规模
对于 40%数据,10<=N<=10,000
对于100%数据,10<=N<=1,000,000,000
对于 100%数据，K<=100,000
输入格式
两个整数N,K，N表示球的个数。
输出格式
输出仅包括一行，一个整数M mod K 。

---

解题思路

因为在考场上忘记矩阵乘法+快速幂加速递推怎么敲了，所以只打了部分分的代码。 但是经过莫名其妙的优化后就能AC

经过前10组数据的推导，可以发现:
$f[N]=1+(3^{n-2}+3^{n-3}+...+3^0)$f[N]=1+(3n−2+3n−3+...+30)
$=\frac{3^{N-1}+1}{2}$=23N−1+1​;
但要对于$K$K取模，如果求$2$2的逆元，当K为偶数时无解

 -----------------------(<<--仅仅会推上面的-->>)

这时候就要用到$(a/b)\% c=(a\% (b*c))/b$(a/b)%c=(a%(b∗c))/b;
具体证明：
设$a=i*b*c+j*b+k;$a=i∗b∗c+j∗b+k;
则原式转换为:
$((i*b*c+j*b+k)/b)\% c=(i*b+j)\% c=j$((i∗b∗c+j∗b+k)/b)%c=(i∗b+j)%c=j;
和$((i*b*c+j*b+k)\% (b*c))/b=(j*b+k)/b=j$((i∗b∗c+j∗b+k)%(b∗c))/b=(j∗b+k)/b=j;
左右相等，证毕。

---

证明来源：https://blog.csdn.net/qq_35479641/article/details/52507337

至于关于矩阵乘法，可参考以下(https://blog.csdn.net/xuxiayang/article/details/83540329)：

---

代码快速幂

#include<cstdio>
using namespace std; 
long long k,n,x=1,y=3;
int main()
{
	scanf("%lld%lld",&n,&k); 
	for (n-=1,k<<=1;n;y=(y*y)%k,n>>=1) if (n&1) x=(x*y)%k; 
	printf("%lld",(x+1)>>1); 
}