微网站建设定制网站建设,wordpress付款下载,通州手机网站建设,咸阳网站制作建设就差一点解题报告descriptionsolutioncodedescription
题目描述
冒泡排序是⼀个简单的排序算法#xff0c;其时间复杂度为O(n2)O(n^2)O(n2)
有⼀个大小为nnn的排列p1,...,pnp_1,...,p_np1,...,pn#xff0c;⼩明想对这个排列进⾏冒泡排序#xff0c;于是写了下⾯这份…
就差一点解题报告descriptionsolutioncodedescription
题目描述
冒泡排序是⼀个简单的排序算法其时间复杂度为O(n2)O(n^2)O(n2)
有⼀个大小为nnn的排列p1,...,pnp_1,...,p_np1,...,pn⼩明想对这个排列进⾏冒泡排序于是写了下⾯这份代码
for(int i1;ik;i)for(int j1;jn;j)if(p[j]p[j1]) swap(p[j],p[j1]);细⼼的选手不难发现小明手抖把第⼀行中的nnn打成了kkk所以当kkk比较小时这份代码可能会出错
⼩明发现当这份代码出错时可能就差⼀点就能把这个排列排序他定义⼀个排列就差⼀点能被排序当且仅当这个排列存在⼀个大小为n−1n-1n−1的上升子序列
小明想知道对于给定的n,kn,kn,k有多少种不同的排列满⾜对这个排列运⾏上述代码后这个排列就差⼀点能被排序
由于答案可能很⼤⼩明只需要知道答案对质数modmodmod取模的结果
输入格式
本题⼀个测试点含有多组测试数据第⼀行⼀个整数TTT表示数据组数
接下来TTT行每行333个整数n,k,modn,k,modn,k,mod意义同题意
输出格式
共TTT行对于每组测试数据输出一行一个整数表示答案
样例
5
5 1 998244353
5 2 998244353
5 3 998244353
5 4 998244353
5 5 99824435374
114
120
120
120数据范围
1≤n,k,T≤5000,108≤mod≤10971\le n,k,T\le5000,10^8\le mod\le 10^971≤n,k,T≤5000,108≤mod≤1097
solution DDG有个神奇DPDPDP正确倒是正确只是这是怎么想到的呢 dpi,j∑k1j−1dpi−1,kj∗dpi,jdp_{i,j}\sum_{k1}^{j-1}dp_{i-1,k}j*dp_{i,j}dpi,j∑k1j−1dpi−1,kj∗dpi,j 前iii个数在xxx前面比xxx大的数的个数最大值为jjj 的序列 因为一次冒泡排序相当于处理了 在iii前面比iii大的数个数最多 的iii 卷爷找了三个强大的性质 最重要的性质就是对于值属于[i,n][i,n][i,n]的所有下标将这些下标抽出来然后根据值离散化 如果离散化后的序列需要ttt次变成单调上升那么回到原序列也只需要ttt次单看这些下标就会发现是单调上升的 结合这两种思路就来到了小儿子的通俗易懂的解法——反序表 反序表对于一个排列的定义为si∑j1i−1[pjpi]s_i\sum_{j1}^{i-1}[p_jp_i]si∑j1i−1[pjpi] 即反序表的第iii位上的数值表示在原排列中第iii位以前的比第iii位值大的个数 e.g. 原序列3 2 4 1 5反序表为0 1 0 3 0 反序表具有很多非常好的性质 显然对于iiisiis_iisii严格小于)换言之对于iii其sis_isi的取值为[0,i)[0,i)[0,i)共iii个 反序表与排列是一一对应的那么原题要求排列个数就转化成了求反序表的个数 冒泡一轮排序会将 最大的 还没在应在位置的值 放置在 其应在位置然后这区间中的每个数位置都会前移一位其在反序表的变化则为下标值均减一如果已经是000就不减 换言之一次冒泡排序后每个数至多只会减少一 e.g. 原序列3 2 5 1 4反序表为0 1 0 3 1 一次冒泡排序后 原序列3 2 1 4 5反序表为0 1 2 0 0 555由位置333变到555反序表改变的区间为[3,5][3,5][3,5] 反序表中iii位置上的值如果为sis_isi意味着至少需要sis_isi次冒泡排序才能将原序列iii有序 这里的有序定义为其前面的数全小于ta其后面的数全大于ta 了解完反序表的性质后就可以解决这道题了 考虑冒泡排序后最后的序列是一个长为nnn的上升子序列不差一点 这时的反序表全是0000,0,0,...,0 一次排序反序表只能减一或者不减kkk次排序最多减少kkk 也就是说想要最后反序表为000其初始值不能超过kkk 即∀isi≤min(i−1,k)\forall_i\quad s_i\le \min(i-1,k)∀isi≤min(i−1,k) 将这些值域限制乘起来就是不同的反序表个数也就是不同的排列个数 即∏i1n(min(i−1,k)1)\prod_{i1}^n\Big(\min(i-1,k)1\Big)∏i1n(min(i−1,k)1) 考虑冒泡排序后最后的序列是一个长为n−1n-1n−1的上升子序列只差一点 这时的反序表形如0,0,...,1,1,...,1,0,0,...,0 e.g. 最后序列为4 1 2 3 5反序表为0 1 1 1 0 最后为000说明初始反序表的值不超过kkk 最后为111说明初始反序表的值不超过k1k1k1 注意sis_isi能取到k1k1k1的iii是有限制的仅为[k2,n][k2,n][k2,n]共n−(k2)1n−k−1n-(k2)1n-k-1n−(k2)1n−k−1个 不要忘记siis_iisii的约束 考虑枚举这段111的长度lenlenlen 这段长度的选择方案相当于在总长为n−k−1n-k-1n−k−1中摆下lenlenlen的放置方案显然为n−k−1−len1n−k−lenn-k-1-len1n-k-lenn−k−1−len1n−k−len种 剩下的n−k−1−lenn-k-1-lenn−k−1−len个数反序表都不超过kkk可选为[0,k][0,k][0,k]共k1k1k1个 这些数生成的反序表组合为(k1)n−k−1−len(k1)^{n-k-1-len}(k1)n−k−1−len再乘上前kkk个数的组合 即(k1)!∗∑i1n−k−1(k1)n−k−1−len∗(n−k−len)(k1)!*\sum_{i1}^{n-k-1}(k1)^{n-k-1-len}*(n-k-len)(k1)!∗∑i1n−k−1(k1)n−k−1−len∗(n−k−len) 这时的反序表有且仅有一个位置其si1s_i1si1严格大于 e.g. 最后序列为2 3 1 4 5反序表为0 0 2 0 0 相当于原始sik1s_ik1sik1这个iii同样有范围限制为[k3,n][k3,n][k3,n] 对于iii其选择方案为i−1−(k2)1i−k−2i-1-(k2)1i-k-2i−1−(k2)1i−k−2 即∑ik3n∏j1n[j≠i](min(j−1,k)1)⋅[ji](i−k−1)\sum_{ik3}^n\prod_{j1}^n[j≠i]\big(\min(j-1,k)1\big)·[ji](i-k-1)∑ik3n∏j1n[ji](min(j−1,k)1)⋅[ji](i−k−1)
code
#include cstdio
#include iostream
using namespace std;
#define maxn 5005
#define int long long
int T, n, k, mod, fac;
int inv[maxn], mi[maxn];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}signed main() {scanf( %lld, T );while( T -- ) {scanf( %lld %lld %lld, n, k, mod );fac inv[1] mi[0] 1;if( k n ) {for( int i 1;i n;i )fac fac * i % mod;printf( %lld\n, fac );continue;}for( int i 1;i k 1;i )fac fac * i % mod;for( int i 2;i k 1;i )inv[i] ( mod - mod / i ) * inv[mod % i] % mod;for( int i 1;i n;i ) mi[i] mi[i - 1] * ( k 1 ) % mod;int ans fac * mi[n - k - 1] % mod;for( int i 1;i n - k - 1;i )ans ( ans fac * ( n - k - i ) % mod * mi[n - k - 1 - i] ) % mod;int mul 1;for( int i 1;i n;i )mul mul * ( min( i - 1, k ) 1 ) % mod;for( int i k 3;i n;i )ans ( ans mul * inv[min( i - 1, k ) 1] % mod * ( i - k - 2 ) ) % mod;printf( %lld\n, ans );}return 0;
}
