牛客手速月赛61 F(又是被20级打爆的一天)
admin
2024-02-01 07:02:44
0次
题目
题意: 放映厅中有n张椅子，f(x)表示有x位观影者的方案数，要求观影者是连续坐的。并且有m条限制，必须同时满足才行。第i条的限制是，ai或bi或ci中至少有一个被观影者坐了。
思路: 考虑到[l,r+1]不会比[l,r]更差，只会不变或者更优。所以我们对于每个l，都可以找到对应的最小的r，长度为r-l+1到n-l+1的方案数+1，这个用差分维护即可。最后求和完记得乘以x的阶乘，因为他们内部可以任意组合。
代码:
#include
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int mod = 1e9+7;
int n,m,k,T;
vector va[N];
int b[N];
int cnt[N];
int now;
void add(int x)
{for(int i=0;iint j = va[x][i];if(++cnt[j]==1){now++;}}
}
void del(int x)
{for(int i=0;iint j = va[x][i];if(--cnt[j]==0){now--;}}
}
void solve()
{cin>>n>>m;for(int t=0;t<3;++t)for(int i=1;i<=m;++i){int x; cin>>x;va[x].push_back(i);}for(int l=1,r=0;l<=n;l++){while(r+1<=n&&nowb[r-l+1]++;b[n-l+2]--;}else break;del(l);}ll fac = 1;for(int i=1;i<=n;++i){fac = fac * i % mod; b[i] = (b[i]+b[i-1]) % mod;cout<<1ll*b[i]*fac%mod<<" ";}
}
signed main(void)
{solve();return 0;
}
上一篇：加拉格尔禁区内倒地，主裁判没有表示 加拉格尔禁区内倒地，主裁判没有表示
下一篇：首球制胜！西甲官方：罗克当选巴萨vs奥萨苏纳全场最佳球员 西甲巴萨逆转奥萨苏纳比赛结果 西甲第十一轮巴塞罗那vs奥萨苏纳
相关内容
热门资讯
一天22个大V账号被封 平台出...
雪球大V“金浤”被罚之后，一天之内，22个大V账号被永久封禁，平台连续出手整治涉资本市场违规行为。 ...
罕见！自砍七成融资规模，百瑞吉...
导读：过去一年中，为了尽快向A股大门靠近，百瑞吉还付出了不小的代价——大幅削减融资规模。近年来，拟北...
氢能商业化难题待解，记者实探云...
本报（chinatimes.net.cn）记者胡雅文 曲靖报道 氢能商业化仍在探索中。 近年来国家和...
原创 西...
哥本哈根街头，上万名示威者举着“绝不出售格陵兰岛”的标语走向美国驻丹麦大使馆，寒冷的北欧空气中弥漫着...
成品油价或年内首涨！
今日(1月20日)24时，国内成品油新一轮调价窗口将开启。综合多家机构预测，成品油价或年内首涨，消费...
原创 电...
外资来了，不是随便逛街，是掏钱出手，高盛、瑞银、摩根士丹利、摩根大通四家都在名单上，其中三家在202...
信用卡分期纳入贴息，多家银行迅...
【大河财立方消息】1月20日，财政部、中国人民银行、金融监管总局发布《关于优化实施个人消费贷款财政贴...
原创 金...
“好家伙，前几天还说金价破纪录了，这转头又掉下来了？这过山车坐的，心脏真受不了。”最近但凡关心点金价...
卖不动了？巨头宣布：降价！10...
自2022年见顶以来，受主要消费国奢侈品消费降温、培育钻石日益走俏等因素影响，钻石行业正遭遇现代史上...
鸣鸣很忙开启招股，2万家店撑起...
1月20日，中国最大的休闲食品饮料连锁零售商——湖南鸣鸣很忙商业连锁股份有限公司（下称“鸣鸣很忙”）...
原创 继...
去年九月的那个深夜，白俄罗斯边境毫无征兆地熄火了，原本跑得飞快的中欧班列，在那一刻被人按下了暂停键。...
供应扰动再发酵，碳酸锂尾盘涨停...
经历了一次急速回调后，碳酸锂期货又杀了一个“回马枪”。 1月20日，碳酸锂期货主力合约在尾盘触及涨停...
原创 融...
2026年伊始，A股市场便以一派火热景象迎接投资者，市场热度在多个维度均有所体现，尤其以融资余额的迅...
财经老王丨140万亿元 跟咱老...
来源：甘肃网络广播电视台 2025年，中国经济总量突破140万亿元。这个数字跟咱们老百姓有啥关系呢？...
小红书奶茶养号秘诀——4288...
大家好，我是4288养号盒子，提供专业免费养号软件，不仅有抖音养号，还有小红薯养号等、还有短视频热门...
原创 干...
美国这些年总想在经济上给中国使绊子，从贸易战打到科技限制，可中国那边经济还是稳稳的往前拱。2018年...
纪念币纪念钞二手交易莫冲动
来源：经济日报 目前，二手市场高价接盘的风险很高。一方面，卖家无实物，且二手市场缺乏权威验货渠道，买...
“十年十亿”魔咒告破？全球巨头...
2026年开年，AI制药正以前所未有的速度冲击传统研发的“双十定律”——一款新药研发需要十年时间、耗...
红杉资本考虑参投Anthrop...
红杉资本正准备加入Coatue和新加坡主权财富基金GIC，参与人工智能初创公司Anthropic P...
大行回应！消费贷贴息政策升级，...
来源：第一财经 消费贷贴息政策迎来重要升级，落地细节备受关注。1月20日晚间，多家国有大行表态将积极...