C - Fair Elevator
题意：一栋楼1~2n层，一个电梯只从下到上一次，要求每层楼只上一个人或者下一个人，问能否成立
思路：预处理[l,r]区间可不可能正好达到要求，最后dp整合，若dp[2*n]可以到达说明有方案成立
对于一个封闭区间[l,r]，一定是由[l,mid]一一对应分别指向[mid+1,r]，只需判断能否做到一一对应即可
成立的情况分四种：1.正好有i~mid+i-l+1这种人
2.有i~-1
3.有-1~mid+i-l+1
4.i与mid+i-l+1都没有出现过并且还剩下两个都是-1的人没有用
D - Multiset Mean
题意：给定n，k，mod，求出一个可重集每个集合元素出现不超过k次且平均值为x（x<=n)的数的个数
一个背包的变形
对于每个x，集合中元素减去i的和为0，及
可以将每个si直接看作si-x，对于负数，看作为他的绝对值
记录dp[i][j]，表示为只选取1~i并且不超过k个数，值为j的个数
每次可以看作正数选dp[n-x]，负数选dp[x-1]，因为和为0，所以第二位应该相等
因为0随便选，乘上（k+1)，最后减掉空集1
#include<bits/stdc++.h>
using namespace std;
int dp[110][1100100];
int a,b,mod;
int add(int x,int y);
int del(int x,int y);
int main(){
scanf("%d%d%d",&a,&b,&mod);
dp[0][0]=1;
int val=a*a*b;
for(int i=1;i<=a;i++){
for(int j=0;j<i;j++){
int sum=0;
deque<pair<int,int> >q;
for(int gs=0;gs*i+j<=val;gs++){//单调队列优化多重dp
while(!q.empty()&&q.front().second+b<gs) sum=del(sum,q.front().first),q.pop_front();
q.push_back({dp[i-1][gs*i+j],gs}),sum=add(sum,dp[i-1][gs*i+j]);
dp[i][gs*i+j]=sum;
}
}
}
for(int i=1;i<=a;i++){
int ans=0;
for(int j=0;j<=val;j++){
ans=add(ans,1ll*dp[a-i][j]*dp[i-1][j]%mod);
}
printf("%d\n",del(1ll*ans*(b+1)%mod,1));
}
return 0;
}
int add(int x,int y){
return (x+y)%mod;
}
int del(int x,int y){
return (x-y+mod)%mod;
}E - Random LIS
题意：一个长度为a的数列每个数不超过ni，求期望最长上升子序列长度
因为a<=6，故枚举所有可能情况
枚举每个数的rank，按照rank排序后变成了：
一堆数可以选1~ai，rank i的大小要大于rank 1~i-1，求情况数
将值域按照ai奋斗
令dp[i][j]表示第i个数选取的是第j段的个数，有
ok(x+1,i,y)是用来判断这一段序列都可以选第y段
最后对于每个结果乘上长度就行，因为求期望，答案再除掉情况数
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int r,rk;
};
node mes[10],now[10];
bool cmp(node x,node y){
return x.rk<y.rk;
}
int mod=1e9+7;
int a,ans,dp[10],tot,ty[10][10];
bool vis[10],use[1010000];
void dfs(int gs,int rk);
int C(int up,int down);
int qpow(int x,int y);
bool ok(int l,int r,int id);
int mp[10],sz;
signed main(){
scanf("%lld",&a);
for(int i=1;i<=a;i++) scanf("%lld",&mes[i].r),mp[i]=mes[i].r;
sort(mp+1,mp+a+1);
sz=unique(mp+1,mp+a+1)-mp-1;
dfs(1,1);
printf("%lld",ans*qpow(tot,mod-2)%mod);
return 0;
}
void dfs(int gs,int rk){
if(gs>a){
int pd=0;
for(int i=1;i<=a;i++) pd=pd*10+mes[i].rk;//判断是否重复
if(use[pd]) return ;
use[pd]=true;
int lis=0;
memset(dp,0,sizeof(dp));
for(int i=1;i<=a;i++){
for(int j=0;j<i;j++){
if(mes[i].rk>mes[j].rk) dp[i]=max(dp[i],dp[j]+1);
}
lis=max(lis,dp[i]);
}
for(int i=0;i<=a;i++) now[i]=mes[i];
sort(now+1,now+a+1,cmp);
memset(ty,0,sizeof(ty));
ty[0][0]=1;
for(int i=1;i<=a;i++){
if(now[i].rk==now[i+1].rk) continue;
for(int j=1;j<=sz;j++){
if(mp[j]>now[i].r) break;
for(int l=0;l<i;l++){
if(now[l].rk==now[l+1].rk) continue;
if(!ok(l+1,i,j)) continue;
for(int las=0;las<j;las++){
ty[i][j]=(ty[i][j]+C(now[i].rk-now[l].rk,mp[j]-mp[j-1])*ty[l][las]%mod)%mod;
}
}
}
}
int nowans=0;
for(int j=1;j<=sz;j++) nowans=(nowans+ty[a][j])%mod;
tot=(tot+nowans)%mod;
ans=(ans+nowans*lis%mod)%mod;
return ;
}
for(int i=1;i<=a;i++){
if(!vis[i]){
vis[i]=true;
mes[i].rk=rk;
if(gs!=a) dfs(gs+1,rk+1);
dfs(gs+1,rk);
vis[i]=false;
mes[i].rk=0;
}
}
}
int C(int up,int down){
if(up>down) return 0;
int ans1=1,ans2=1;
for(int i=1;i<=up;i++) ans1=ans1*i%mod;
for(int i=down-up+1;i<=down;i++) ans2=ans2*i%mod;
return ans2*qpow(ans1,mod-2)%mod;
}
int qpow(int x,int y){
int ans=1;
while(y){
if(y&1) ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
bool ok(int l,int r,int id){
for(int i=l;i<=r;i++){
if(now[i].r<mp[id]) return false;
}
return true;
}