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

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

背景

刺猬头：

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

题面

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

N ≤ 1 0 9 , M ≤ 10 , P ≤ 1000 Nleq 10^9,Mleq 10,Pleq 1000 N≤109,M≤10,P≤1000 。

题解

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

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

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

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;
}