怎么学会建自己网站的方法,深圳微信网站建设报价,图片外链网站,网站建设一条龙源码C - Insertion Sort Gym - 101955C
题意#xff1a;
t组数据#xff0c;每组数据给你n#xff0c;k#xff0c;q#xff0c;让你求存在多少合法的1~n排列 合法要求#xff1a; 对排列的前k项进行排序#xff0c;使得整个序列中最长的递增子序列长度为n-1
题解#x…C - Insertion Sort Gym - 101955C
题意
t组数据每组数据给你nkq让你求存在多少合法的1~n排列 合法要求 对排列的前k项进行排序使得整个序列中最长的递增子序列长度为n-1
题解
肯定是公式题利用组合数来推公式但是我太菜了emm 打表得到横坐标为n纵坐标为k 代码代码 然后就是对着表找规律上下做差可以得到下图发现每列数都是等差数列第一列等差为2第二列为4第三列为12第四列为48。。。 继续找规律我们发现首项都是i * i差为2 * i 在第一个图中对角线的数是K然后往下就是等差数列的和 比如第n行第k列nk,第k行第k列是K然后往下n-k个数 “等差数列求和SnN*a1N(N-1)d/2或SnN(a1an)/2 d 2 * k a1k * k N n-k 带入得 Sn (n-k) * (k * k!) (n-k) * (n-k-1) *(2 * k!) /2 记得还要加上K起始数 化简得 k!(n2 - (k1)nk1)
代码
#includebits/stdc.h
using namespace std;
#define int long long
typedef long long ll;int n, m , mod;signed main() {int cas;int tt 1;cin cas;while(cas --) {cin n m mod;int k 1;if(m n - 1) m n;for(int i 2; i m; i ) {k * i % mod;k % mod;}cout Case # tt : ;if(m n - 1) cout k endl;else cout (k)*(n * n % mod - (m 1) * n % mod m 1 mod) % mod endl;}return 0;
}
