一句话题意：三维空间划分四维空间，最多能划分成多少个部分。
我们直接想四维的不好想，但是一般这种题我们考虑从低维开始做起。
在经过手算之后我们可以发现：
设\(f(x)\)为零维（点）切一维（线）最多划分的部分，递推式：\(f(x)=f(x-1)+1\)
设\(g(x)\)为一维（线）切二维（平面）最多划分的部分，递推式：\(g(x)=g(x-1)+f(x-1)\)
设\(k(x)\)为二维（平面）切三维（空间）最多划分的部分，递推式：\(k(x)=k(x-1)+g(x-1)\)
设\(h(x)\)为三维（空间）切四维最多划分的部分，递推式：\(h(x)=h(x-1)+k(x-1)\)
那么我们很容易看出这是一个递推。但是因为数据范围很大，所以我们考虑构造矩阵进行矩阵快速幂加速运算。（不会打mathjax矩阵，只能凑合一下了）
1 1 0 0 0
0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1然后初始矩阵[1,f(0),g(0),k(0),h(0)]
但是因为数据实在很大，矩阵快速幂进行乘的时候很可能炸long long，所以我们用快速乘来保证数在mod范围内。
代码如下：
#include#include #include #include #define MAXN 40using namespace std;long long n,m;long long f[MAXN];struct Node{long long t[MAXN][MAXN];};Node init;inline long long multi(long long x,long long y,long long mod){ long long ans=0; while(y) { if(y&1) ans=(ans+x)%mod; x=(x+x)%mod; y>>=1; } return ans%mod;}inline Node mul(Node x,Node y){ Node cur; for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) cur.t[i][j]=0; for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) for(int k=1;k<=5;k++) cur.t[i][j]=(cur.t[i][j]+multi(x.t[i][k],y.t[k][j],m))%m; return cur;}inline void solve(){ long long cur[MAXN]; memset(cur,0,sizeof(cur)); for(int j=1;j<=5;j++) for(int k=1;k<=5;k++) cur[j]=(cur[j]+multi(f[k],init.t[k][j],m))%m; for(int i=1;i<=5;i++) f[i]=cur[i];}int main(){ freopen("discover.in","r",stdin); freopen("discover.out","w",stdout); scanf("%lld%lld",&n,&m); f[1]=1; f[2]=1; f[3]=1; f[4]=1; f[5]=1; for(int i=1;i<=5;i++) init.t[i][i]=1; init.t[1][2]=1; init.t[2][3]=1; init.t[3][4]=1; init.t[4][5]=1; while(n) { if(n&1) solve(); init=mul(init,init); n>>=1; } printf("%lld\n",f[5]%m); return 0;}