牛客手速月赛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奥萨苏纳
相关内容
热门资讯
我国首个全国产控制系统水光互补...
据国资委官网消息，近日我国首个全国产控制系统水光互补项目——华能小湾水光互补项目在云南正式投运，标志...
2026快手创新与知识产权白皮...
快手以技术创新链与产业应用链双螺旋为核心架构，搭配知识产权支撑体系，形成 AI 时代完整的创新与价值...
被救活了！澳洲这个知名网购平台...
好消息！Click Frenzy被救活啦！ Click Frenzy，是澳洲一个线上大促平台，前段时...
追觅CEO俞浩一天发了117条...
近日，追觅科技CEO俞浩在个人社交平台开启超高强度更新模式。短短三天时间里，他在多个社交平台密集发布...
“红利+”策略指数走势分化，价...
5月6日早盘，市场震荡上行，科技成长方向表现强势，“红利+”策略指数走势分化。截至午间收盘，国证自由...
工业增加值增速创五年新高 福田...
凭借在人工智能领域的深耕，企业扎堆的福田区的天使荟·千模应用加速器不仅摘得深圳多项荣誉，更于近日获评...
原创 敢...
大家好，我是言叔。最近，79岁的“玻璃大王”曹德旺在公开场合放出一句霸气十足的狠话——面对美国可能加...
原创 丧...
溃败边缘狗急跳墙！泽连斯基攻击自家核电站，要拉欧洲同归于尽。战场即将崩盘、停战必死无疑，泽连斯基早已...
A股大涨，超4000只个股上涨...
五一小长假后首个交易日，A股三大指数集体高开，其中，上证指数高开0.57%，深证成指高开1.43%，...
五粮液的大戏，只是拉开序幕
4月30日，赶在五一假期前最后一个交易日，趁着全国人民准备出门旅游的当口，五粮液甩出了多份公告。 其...
原创 存...
这几天发生了不少大事，我们简单捋一捋。三部门放大招，要扩大科技创新贷款投放。 美国对欧盟汽车加征25...
A2奶粉因检出“呕吐毒素”在美...
北京5月5日电(记者 赵方园)新西兰乳企a2牛奶公司卷入蜡样芽孢杆菌毒素召回风波。 5月3日晚，中国...
新股消息 | 从招股书看好医生...
智通财经APP获悉，当市场仍习惯用“传统互联网医疗平台”甚至“传统医药流通渠道”来理解好医生云医疗时...
科创50指数大涨超8% 半导体...
上证报中国证券网讯 5月6日，A股主要股指早盘集体走强。截至午间收盘，沪指涨1.27%，深证成指涨2...
体验经济蓬勃发展，“五一”假期...
今年劳动节假期，部分省市放春假提前预热“假日经济”，传统热门目的地客流量持续增长，曾经的“小众目的地...
互学互鉴促合作 携手共赢谋发展...
5月4日，新乡市工商联“新商课堂”九期班开展企业互访活动。 首站参访了新乡市瑞龙商贸有限公司，该企...
港股异动｜诺比侃大跌15.8%...
诺比侃(2635.HK)大幅下跌15.8%，现报20.24港元股价再度逼近上市低位，市值76.7亿港...
文远知行股权曝光：韩旭持股6....
雷递网 雷建平 5月6日 文远知行（WeRide）日前发布截至2025年12月31日的年报。年报显示...
马斯克同意支付超1000万元罚...
美国证券交易委员会（SEC）与马斯克就收购推特期间的违规诉讼达成和解，相关法庭文件正式提交。 根据协...
大盘放量上攻，全市场半日成交额...
5月6日早盘，A股三大指数集体走强，沪指涨1.27%，冲击五连阳，全市场成交额超2万亿元，较上一交易...