【模拟赛】刺猬头（矩阵优化）

背景

刺猬头：

梦想：成为一名普通高中生。

题面

定义一个排列中所有满足左右的数都比自己小（最左端和最右端也可以算）的位置为刺猬头，求长度为 $N$ 的有恰好 $M$ 个刺猬头的排列个数，对 $P$ 取模。

$N\le 10^9,M\le 10,P\le 1000$ 。

题解

两个刺猬头中间一定会存在一个区间最小值垫底，我们可以按权值从大到小塞入刺猬头或者垫底者。

令 $dp[i][j][k]$ 表示从大到小放入了 $i$ 个数，其中有 $j$ 个刺猬头，$j-k$ 个垫底者的方案数。转移我们就考虑新来的数当刺猬头（加在最左或最右或相邻刺猬头中间原本拿来作垫底者的位置（填了一个，造了两个）），当垫底者（加在相邻刺猬头中间），或是当炮灰（加在每个刺猬头的左边底或右边底）：
$$\begin{gathered} dp[i][j][k]\ast (k+1)\to dp[i+1][j+1][k+1] \\ dp[i][j][k]\ast (k-1)\to dp[i+1][j][k-1] \\ dp[i][j][k]\ast 2k\to dp[i+1][j][k] \end{gathered}$$

这是个状态数 $N\times M\times M$ 的 DP，且转移都是线性变换，所以我们可以用矩阵优化，时间复杂度 $O(M^6\log N)$ 。

CODE

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
int xchar() {static const int maxn = 1000000;static char b[maxn];static int pos = 0,len = 0;if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);if(pos == len) return -1;return b[pos ++];
}
//#define getchar() xchar()
LL read() {LL f = 1,x = 0;int s = getchar();while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
void putnum(LL x) {if(!x) {putchar('0');return ;}if(x<0) putchar('-'),x = -x;return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}int n,m,s,o,k;
int MOD = 1;
int id[15][15];
struct mat{int s[100][100],n,m;mat(){memset(s,0,sizeof(s));n=m=0;}
}A,B;
mat operator * (mat a,mat b) {mat c; c.n = a.n; c.m = b.m;for(int i = 0;i < a.n;i ++) {for(int k = 0;k < a.m;k ++) {if(a.s[i][k])for(int j = 0;j < b.m;j ++) {c.s[i][j] = (c.s[i][j] + a.s[i][k]*b.s[k][j]) % MOD;}}}return c;
}
int main() {freopen("queue.in","r",stdin);freopen("queue.out","w",stdout);n = read();m = read();MOD = read();int cn = 0;for(int i = 1;i <= m;i ++) {for(int j = 1;j <= i;j ++) {id[i][j] = cn ++;}}A.n = 1; A.m = B.n = B.m = cn;A.s[0][id[1][1]] = 1;for(int j = 1;j <= m;j ++) {for(int k = 1;k <= j;k ++) {if(j < m) (B.s[id[j][k]][id[j+1][k+1]] += k+1) %= MOD;if(k > 1) (B.s[id[j][k]][id[j][k-1]] += k-1) %= MOD;(B.s[id[j][k]][id[j][k]] += 2*k) %= MOD;}}n --;while(n > 0) {if(n & 1) A = A*B;B = B*B; n >>= 1;}AIput(A.s[0][id[m][1]],'\n');return 0;
}