当前位置：首页 > news >正文

打卡信奥刷题（3289）用C++实现信奥题 P8962 「WHOI-4」yadiw. Slua, gassp, lhtubs.

news 2026/9/6 17:54:59

P8962 「WHOI-4」yadiw. Slua, gassp, lhtubs.

题目背景

If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

题目描述

小 F 有一个奇妙的数组aaa，aaa中没有重复的元素，长度为nnn，他使用std::sort将他排序了，认为它是有序的，所以他正在使用这样的方法进行二分查找。显然，能否查到只和数列的离散化结果有关，所以你可以直接把aaa看作1∼n1\sim n1∼n的一个排列。

intsearch(intkey){intl=1,r=n;while(l<=r){intmid=(l+r)/2;if(a[mid]<key)l=mid+1;elseif(a[mid]==key)returnmid;elser=mid-1;}return-1;}

不幸的是，小 W 为了让他戒掉万能头，在bits/stdc++.h中写了#define sort random_shuffle，这意味着aaa实际是一个随机的排列。

现在，对于所有在111到NNN范围内的nnn，以及所有在111到nnn范围内的kkk，在aaa数列的所有排列中，有几个可以正确地找到第kkk小的元素keykeykey（即返回值非−1-1−1）？由于答案可能过大，请输出它对给定模数ppp取模的结果。

输入格式

一行两个正整数p,Np,Np,N。

输出格式

NNN行，第nnn行nnn个正整数，代表在nnn个元素中找kkk能找到的方案数。

输入输出样例 #1

输入 #1

998244353 5

输出 #1

1 1 2 4 4 4 12 12 14 18 48 54 60 66 72

说明/提示

数据范围

本题采用 Subtask 评测。

Subtask 1（101010pts）：N=10N=10N=10，$ p\ge998244352$；
Subtask 2（252525pts）：N=100N=100N=100，p≥1009p\ge1009p≥1009且为素数；
Subtask 3（252525pts）：N=400N=400N=400，p≥1009p\ge1009p≥1009且为素数；
Subtask 4（404040pts）：N=400N=400N=400。

对于所有数据，10≤N≤40010\le N\le 40010≤N≤400，$ 2\le p\le998244353$。

C++实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintMAXN=4e2+10;intn,mod;ll ans[MAXN],fac[MAXN],c[MAXN][MAXN];intmain(){scanf("%d%d",&mod,&n),*fac=1;for(inti=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;for(inti=0;i<=n;i++)c[i][0]=1;for(inti=1;i<=n;i++){for(intj=1;j<=n;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;}for(intm=1;m<=n;m++){for(inti=1;i<=m;i++)ans[i]=0;for(intk=1,l,r,mid,x,y,t;k<=m;k++){l=1,r=m,x=y=0;while(l<=r){mid=l+r>>1;if(mid==k)break;k<mid?(r=mid-1,y++):(l=mid+1,x++);}t=fac[m-x-y-1]%mod*fac[x]%mod*fac[y]%mod;for(inti=x+1;i<=m-y;i++){ans[i]=(ans[i]+c[i-1][x]*c[m-i][y]%mod*t%mod)%mod;}}for(inti=1;i<=m;i++)printf("%lld ",ans[i]);puts("");}}