Educational Codeforces Round 127
F. Permutation Counting
https://codeforces.com/contest/1671/problem/F
t 组测试
问 [1~n]的所有排列中
x个相邻逆序对, k个逆序对 有多少个, 答案取mod 998244353
范围
t <= 3e4 组测试
n <= 998244353 - 1
k <= 11
x <= 11
4s
512MB
题解
k和x很小, 所以不在它原本位置的数字少, 且离原来位置也近
直接暴力算出 12! 的所有排列,记录 其中 (k,x) 和长度
那么答案相当于 把这些排列 插入到有序数字中
所以 再计算一个组合数
需要注意的是, [1~10] 的排列 可能是由 [1-4][1-6] 的排列组成的, 所以 要注意不可分割的排列统计, 或者插入的时候 不支持相邻
代码
无
总结
暴力和关联性的思路对了, 但为啥我在想矩阵乘法而不是组合数,让我自己卡住了