「KDOI」Round 2 | CSP-S 组模拟赛

这场比赛的梯度相对上一场比赛较小，没有断崖式的难度跨越，但是每一题都很难（2蓝1紫1黑），远远超出了CSP-S的难度。所以我虽然只有15pts，但是却进了前10%。下面对这些题目进行赛后总结：

这题看起来是一个物理题啊。通过对于平抛运动的学习，可以发现：只有处于同一水平线（y相等）上的点才会相碰，那么我们就可以发现：对于两个y相等的点，若出发点在前的点的落地点在出发点在后的点的落地点之后，二者必然会相碰。然后我们敏感地察觉到：这就是逆序对。一个导弹地威力大小，就是其与前后的数构成的逆序对的个数。我们之前学过归并排序求逆序对个数，但那是求整个区间的逆序对个数。而对于在给定区间内求每个数与其它数构成的逆序对个数，则是一个动态问题，需要维护树状数组来解决。但是我代码能力比较差，写不出好代码，只能抄袭题解。

T2：一个仇的复（极其困难）
这个名字听上去很高级，实际上可以用组合数的意义解释）。

那么再考虑放置了竖着的矩形的情况：假设当前已经选了j个竖着的矩形。由于j个矩形可以相连，所以划分开的子矩形的个数并不确定，所以设一共有i个空的子矩形。那么这j个竖矩形就将整个2×n的矩形划分为了i个子矩形：可以统计一共有种选法（因为左右两边可能也放置了竖矩形）。那么这时我们还需要固定子矩形的排列顺序，也就是求出将剩下的n-j个单位矩形分给余下的子矩形，那么一共有种选法。那么最后考虑具体每个矩形内的安排方法：也就是将剩下的k-j个可安排的矩形安排到每一个空的子矩形之中。设所有空的子矩形的长度分别为……，安排进去的剩余矩形数分别为……。那么由第一段的推论可知：这里的选法数为：，再由第一段的范德蒙德卷积可知：式子可化为：。

那么综上所述，最终答案为。但是最后还要判断n是否等于k，若等于，则还要加上1。（因为还可能是放n个竖着的矩形）。代码如下：

#include<iostream>
using namespace std;
const int N=4e7+5,mod=998244353;
typedef long long ll;
int fac[N],inv[N];
int qmi(int a,int b,int p){
int res=1;
while(b){
if(b&1) res=(ll)res*a%p;
a=(ll)a*a%p;
b>>=1;
}
return res%p;
}
void init(){
fac[0]=1;
for(int i=1;i<=40000000;i++){
fac[i]=((long long)fac[i-1]*i)%mod;
}
inv[40000000]=qmi(fac[40000000],mod-2,mod);
for(int i=39999999;i>=0;i--){
inv[i]=((long long)inv[i+1]*(i+1))%mod;
}
//这种求逆元的方法仅仅只要求一次快速幂即可，大大提高了效率
}
ll C(int b,int a){
return (ll)((ll)fac[b]*inv[b-a]%mod)*inv[a]%mod;
}
int main(){
init();
int n,k;
cin>>n>>k;
ll ans=0;
for(int i=1;i<=k;i++){
for(int j=0;j<=k&&k-j-2*i>=0;j++){
if(2*(n-i-j)<0||k-j-2*i<0||n-j-1<0||2*(n-i-j)<k-j-2*i||j+1<i||n-j-1<i-1) continue;
ans=(ans+((long long)(C(2*(n-i-j),k-j-2*i)*C(j+1,i)%mod)*(long long)C(n-j-1,i-1)%mod))%mod;
}
}
cout<<(ans+(n==k))%mod;
return 0;
}

T3： 一个网的路

最后

以上就是秀丽金针菇为你收集整理的「KDOI」Round 2 | CSP-S 组模拟赛的全部内容，希望文章能够帮你解决「KDOI」Round 2 | CSP-S 组模拟赛所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。