woj4790~4792
状态不好，当庭GG
考场脑残，实际上是个很弱的sort二分题。题意告诉我们重复的不用多算，那直接加就行。
按%mod余数sort，对于同一个数，选择了，那cnt要-1，如果为0就说明用完了不能用。
注意二分边界，注意卡常。
#include<bits/stdc++.h>
using namespace std;
#define in read()
#define int long long
int in{
int cnt=0,f=1;char ch=0;
while(ch<'0'||ch>'9'){
ch=getchar();if(ch=='-')f=-1;
}
while(ch>='0'&&ch<='9'){
cnt=(cnt<<3)+(cnt<<1)+ch-48;
ch=getchar();
}return cnt*f;
}
int n,mod;
int a[2335];
struct node{
int key,cnt,res;
}t[2335];int cnt;
int ksm(int a,int b){
int sum=1;while(b){
if(b&1)sum=sum*a%mod;b>>=1;a=a*a%mod;
}return sum;
}
bool cmm(node a,node b){
return a.res<b.res;
}
int sum[2335];int ans;
int A,B;
void exgcd(int a,int b,int &x,int &y){
if(!b){
x=1;y=0;return;
}exgcd(b,a%b,y,x);
y-=a/b*x;
}
signed main(){
n=in;mod=in;for(register int i=1;i<=n;++i)a[i]=in;
sort(a+1,a+n+1);
for(register int i=1;i<=n;++i){
if(a[i]!=a[i-1]){
t[++cnt]={a[i],1,a[i]%mod};
}else t[cnt].cnt++;
}int x,y,z;
//for(register int i=1;i<=cnt;++i)cout<<t[i].key<<" "<<t[i].cnt<<endl;
sort(t+1,t+cnt+1,cmm);
for(register int i=1;i<=cnt;++i){
x=t[i].cnt;--t[i].cnt;
for(register int j=i;j<=cnt;++j){
if(!t[j].cnt)continue;
y=t[j].cnt--;//cout<<t[i].key<<" "<<t[j].key<<" ";
int mul=t[i].res*t[j].res%mod;
exgcd(mul,mod,A,B);mul=(A%mod+mod)%mod;//cout<<mul<<endl;
int l=j;int r=cnt;int as1,as2;
while(l<r){//大于等于给定值的最小值
int mid=(l+r)>>1;
if(t[mid].res>=mul)r=mid;
else l=mid+1;
}as1=l;
if(!t[as1].cnt)as1++;
l=j;r=cnt;//cout<<l<<" "<<r<<endl;
while(l<r){//大于给定值的最小值
int mid=(l+r+1)>>1;
if(t[mid].res>mul)r=mid-1;
else l=mid;
} as2=l;//cout<<t[i].key<<" "<<t[j].key<<" "<<as1<<" "<<as2<<" "<<t[as1].res<<endl;
if(t[as1].res!=mul){
++t[j].cnt;continue;
}
if(as1>as2){t[j].cnt++;continue;}
z=as2-as1+1;//cout<<t[i].key<<" "<<t[j].key<<" "<<t[as1].key<<" "<<t[as2].key<<endl;
//cout<<t[i].key<<" "<<t[j].key<<" "<<t[as1].key<<" "<<t[as2].key<<endl;
ans+=as2-as1+1;
++t[j].cnt;
}
}cout<<ans;
return 0;
} 本质是个二维偏序最长不下降，但有个背包限制很恶心。这个不是考场脑残，只是太菜而想不到怎么解决限制。
我们发现，肯定选大的背包好。那在查询的时候，注意当前能用的背包数量和最长不下降序列长度取min。
为了方便，我们倒序sort。为了习惯，我给value赋的是rank。
#include<bits/stdc++.h>
using namespace std;
#define in read()
#define int long long
int in{
int cnt=0,f=1;char ch=0;
while(!isdigit(ch)){
ch=getchar();if(ch=='-')f=-1;
}
while(isdigit(ch)){
cnt=cnt*10+ch-48;ch=getchar();
}return cnt*f;
}
struct node{
int w,v;
}a[100003];
int bag[100003];
int b[100003],bcnt,ans;
int n,m;
struct bili{
int t[100003];
int lowbit(int x){
return x&(-x);
}
void modify(int x,int key){
while(x<=n){
t[x]=max(t[x],key);x+=lowbit(x);
}
}
int query(int x){
int sum=0;
while(x){
sum=max(sum,t[x]);x-=lowbit(x);
}return sum;
}
}t;
bool cm(int a,int b){
return a>b;
}
bool cmm(node a,node b){
if(a.w!=b.w)return a.w<b.w;return a.v>b.v;
}
signed main(){
int T=in;
while(T--){bcnt=0;
memset(t.t,0,sizeof(t.t));n=in;
for(int i=1;i<=n;i++){
a[i].w=in;a[i].v=in;b[++bcnt]=a[i].v;
}sort(b+1,b+bcnt+1);bcnt=unique(b+1,b+bcnt+1)-b-1;
for(int i=1;i<=n;i++)a[i].v=lower_bound(b+1,b+bcnt+1,a[i].v)-b,a[i].v=bcnt-a[i].v+1;
m=in;for(int i=1;i<=m;i++)bag[i]=in;
sort(bag+1,bag+m+1,cm);sort(a+1,a+n+1,cmm);
//for(int i=1;i<=n;i++)cout<<a[i].w<<" "<<a[i].v<<endl;
// cout<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl;
// for(int i=1;i<=m;i++)cout<<bag[i]<<" ";cout<<endl;
int pos=0;ans=0;
for(int i=n;i>0;i--){
while(pos<m&&bag[pos+1]>=a[i].w)++pos;
int key=t.query(a[i].v);key=min(key+1,pos);
ans=max(ans,key);t.modify(a[i].v,key);
}cout<<ans<<'\n';
}
return 0;
}唯一一道做出来的题，因为组合数位忘了取模而44滚粗了。
对于这类计数问题，为了不重不漏，我们很明显要寻找一个固定的子结构来转移状态。
我们发现，因为是个编号大根堆，所以次小序号，一定连着根节点。
那我们枚举次小点的子树大小，然后标号即可。
令
表示……哎呀，发现一个问题。如果子树深度刚好是j-1，其它子树就没必要达到j。而如果其它子树达到了j，那次小子树就没必要达到j-1。
GG，选择修改状态定义。
令
所以
组合数的意义是，去掉根节点和次小节点，我们还需要k-1个点去成为次小子树。因为本身有编号限制，所以直接选出来不需要在意顺序。
但是要注意，我们的状态设置是深度前缀和，我们必须从深度开始枚举，否则会有后效性。
//尝试列方程
//发现次小必须接自己的性质。
//发现方程列不动。次小可能深度为j，但别的子树也可能深度为j。
//考虑差分？，令j意义变为深度最大限制。
//合并子树最大j-1，其它子树最大j。方程可列。
//f[i][j]=\sum_{k=1}^{i-1} f[k][j-1]*f[i-k][j]*C(i,k)。
//从中选择一些号码出来做新子树。
#include<bits/stdc++.h>
using namespace std;
#define in read()
#define int long long
int in{
int cnt=0,f=1;char ch=0;
while(!isdigit(ch)){
ch=getchar();if(ch=='-')f=-1;
}
while(isdigit(ch)){
cnt=cnt*10+ch-48;
ch=getchar();
}return cnt*f;
}
int f[503][503];
int n,k,a[503];
int c[503][503];
int vis[503];
const int mod=998244353;
signed main(){
// freopen("subtree.in","r",stdin);
// freopen("subtree.out","w",stdout);
n=in;k=in;for(int i=1;i<=k;i++)vis[a[i]=in]=1;sort(a+1,a+k+1);
for(int i=0;i<=500;i++)c[i][0]=1;
for(int i=1;i<=500;i++)for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
// for(int i=0;i<=n;i++){
// for(int j=0;j<=i;j++)cout<<c[i][j]<<" ";cout<<endl;
// }
f[1][1]=1;
for(int j=2;j<=n;j++){f[1][j]=1;
for(int i=2;i<=n;i++){
for(int kk=1;kk<i;kk++){
f[i][j]=(f[i][j]+f[kk][j-1]*f[i-kk][j]%mod*c[i-2][kk-1]%mod)%mod;
}
}
for(int i=1;i<=k;i++){
f[a[i]][j]=0;
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++)cout<<f[i][j]<<" ";cout<<endl;
// }
int l=in;int r=in;
// for(int i=l;i<=r;i++)cout<<f[n][i]<<" "; cout<<endl;
for(int i=l;i<=r;i++)cout<<(f[n][i]-f[n][i-1]%mod+mod)%mod<<" ";
return 0;
}
因篇幅问题不能全部显示，请点此查看更多更全内容