汕头云建站模板,学做甜点的网站,做网站手机验证收费吗,app平台下载题目传送门
引
很有意思的计数题
解法
考虑经过操作后得到的排列的性质 性质1#xff1a; 设 p r e ( i ) pre(i) pre(i):前i个位置的最大值#xff0c;则不会出现超过3个的连续位置的 p r e pre pre相同 必要性#xff1a; 考虑反证#xff0c;若有超过 3 3 3个的连续…题目传送门
引
很有意思的计数题
解法
考虑经过操作后得到的排列的性质 性质1 设 p r e ( i ) pre(i) pre(i):前i个位置的最大值则不会出现超过3个的连续位置的 p r e pre pre相同 必要性 考虑反证若有超过 3 3 3个的连续位置的 p r e pre pre相同那么至少有连续有连续三次选择了比第一次选择要小的数那么至少一个块的长度为 4 4 4,题目中规定块长为 3 3 3因此不合法 充分性 发现没有充分性比如 { 2 , 1 , 4 , 3 , 6 , 5 } \{2,1,4,3,6,5\} {2,1,4,3,6,5},手玩模拟一下就会发现有问题 性质2 若排列总长为 3 N 3N 3N, i i i个的连续位置的 p r e pre pre相同的个数为 c n t i cnt_i cnti,那么 c n t 2 ≤ N − c n t 3 cnt_2\le N-cnt_3 cnt2≤N−cnt3 必要性 对于 c n t 2 cnt_2 cnt2与 c n t 3 cnt_3 cnt3来说他们对应的块内的大小关系是一定的所以可得 c n t 2 c n t 3 ≤ N cnt_2cnt_3\le N cnt2cnt3≤N,移项就行了 我们可以化简 c n t 2 ≤ N − c n t 3 ⇒ 3 c n t 2 ≤ 3 N − 3 c n t 3 ⇒ 3 c n t 2 ≤ ( c n t 1 2 c n t 2 3 c n t 3 ) − 3 c n t 3 ⇒ 移项得 c n t 2 ≤ c n t 1 \begin{aligned} cnt_2\le N-cnt_3\\ \Rightarrow3cnt_2\le 3N-3cnt_3\\ \Rightarrow3cnt_2\le (cnt_12cnt_23cnt_3)-3cnt_3\\ \Rightarrow^{移项得}cnt_2\le cnt_1 \end{aligned} ⇒⇒⇒移项得cnt2≤N−cnt33cnt2≤3N−3cnt33cnt2≤(cnt12cnt23cnt3)−3cnt3cnt2≤cnt1
最后我们发现性质1和性质2加起来就有了充分性 状态设计 f i , j : 前 i 个数 c n t 1 − c n t 2 j 的方案数 f_{i,j}:前i个数cnt_1-cnt_2j的方案数 fi,j:前i个数cnt1−cnt2j的方案数 显然 a n s ∑ k 0 3 n f 3 n , k ans\sum_{k0}^{3n} f_{3n,k} ans∑k03nf3n,k
状态转移
考虑从小到大放数对放 1 / 2 / 3 1/2/3 1/2/3个数分别考虑 f i , j → f i 1 j 1 f i , j → f i 2 , j − 1 ∗ ( i − 1 ) f i , j → f i 3 j ∗ ( i − 1 ) ∗ ( i − 2 ) \begin{aligned} f_{i,j}\to f_{i1j1}\\ f_{i,j}\to f_{i2,j-1}*(i-1)\\ f_{i,j}\to f_{i3j}*(i-1)*(i-2) \end{aligned} fi,j→fi1j1fi,j→fi2,j−1∗(i−1)fi,j→fi3j∗(i−1)∗(i−2) 就好了
code:
#includebits/stdc.h
using namespace std;
const int N 2e3 7, M N * 3;
typedef long long ll;
int n,mod,ans;
int f[M][M1];
int ad(int x,int y){ return (1ll*x1ll*y)%mod; }
void work(int i,int j){f[i1][j1M]ad(f[i1][j1M],f[i][jM]);f[i2][j-1M]ad(f[i2][j-1M],1ll*f[i][jM]*(i1)%mod);f[i3][jM]ad(f[i3][jM],1ll*f[i][jM]*(i1)%mod*(i2)%mod);
}
int main() {scanf(%d%d,n,mod); nn*3;f[0][M]1;for(int i0;in;i) for(int j-i;ji;j) work(i,j);for(int i0;in;i) ansad(ans,f[n][iM]);printf(%d\n,ans);
}TXL
