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

CSP-S模拟29

前言:

如果这场比赛的目的是让我罚坐的话,那它很成功了。半成品...

T1:一个赢家(card)

思路:

显然,最大值的取值范围为\([2n+1,4n-1]\),我们设最大值为\(x\),则对于每种\(x\),有\(⌈\frac{4n-x}{2}⌉\)种构成。我们令\(cnt=⌈\frac{4n-x}{2}⌉\),不妨钦定其中一种为唯一的最大值

T2:排列计数(count)

思路:

显然,要把每个数本身含有的平方数先除掉,然后问题就演变成了对于一个序列,有多少种方案能使相同的数不相邻。这是我们只关注数是否相同,因此我们可以先离散化一下,然后统计每种数出现的次数。接下来考虑\(dp\)。设\(f_{i,j}\)表示放入第\(i\)种数有\(j\)个数不合法的。显然,最后我们要的是\(f_{siz,0}\)\(siz\)为数的种类。考虑如何转移:我们设\(cnt_i\)表示第\(i\)种数的次数,转移方程为

\[f[i][j-x+cnt[i]-k-1]=(f[i][j-x+cnt[i]-k-1]+f[i-1][j]*C(cnt[i]-1,k)%mod*C(j,x)%mod*C(s[i-1]+1-j,k+1-x))%mod; \]

啥意思捏?就是用当前元素插入不合法的数之间减少\(x\)个不合法的数,有新增\(cnt_i-k\)个不合法的数。我们从\(cnt_i\)个数中选出\(k\)个数将从\(j\)个树中选出的\(x\)个数隔开,然后剩下的\(k-x\)个数插入\(s_{i-1}-j+1\)个合法的数的空隙之间,这样不会产生不合法的数。最后因为数字的下标不同表示的方案不同,所以我们在乘上每种数的全排列的方案数就好啦~~

代码:

$code$
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=605,mod=1e9+7;
int T,n,a[N],b[N],ans,num[N],fac[N],inv[N],s[N],cnt[N],f[N][N];
inline int qpow(int x,int y){int res=1;x%=mod;while(y){if(y&1) res=(res*x)%mod;x=(x*x)%mod;y>>=1;}return res;
}
inline int C(int n,int m){if(n<m) return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){freopen("count.in","r",stdin);freopen("count.out","w",stdout);ios::sync_with_stdio(false);fac[0]=1;for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;inv[N-1]=qpow(fac[N-1],mod-2)%mod;for(int i=N-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;cin>>T;while(T--){cin>>n;ans=0;for(int i=1;i<=n;i++) cnt[i]=0;for(int i=1;i<=n;i++){cin>>a[i];int x=a[i];for(int j=2;j*j<=a[i];j++) while(x%(j*j)==0) x/=(j*j);a[i]=x;b[i]=x;}sort(b+1,b+1+n);int siz=unique(b+1,b+1+n)-b-1;for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+1+siz,a[i])-b;cnt[a[i]]++;}for(int i=1;i<=siz;i++) s[i]=s[i-1]+cnt[i];for(int i=0;i<=siz;i++) for(int j=0;j<=n;j++) f[i][j]=0;f[0][0]=1;for(int i=1;i<=siz;i++){for(int j=0;j<=n-siz;j++){if(!f[i-1][j]) continue;for(int k=0;k<cnt[i];k++){for(int x=0;x<=min(j,k+1);x++){f[i][j-x+cnt[i]-k-1]=(f[i][j-x+cnt[i]-k-1]+f[i-1][j]*C(cnt[i]-1,k)%mod*C(j,x)%mod*C(s[i-1]+1-j,k+1-x))%mod;}}}}ans=f[siz][0];for(int i=1;i<=siz;i++) ans=(ans*fac[cnt[i]])%mod;cout<<ans<<'\n';}return 0;
}
http://www.hskmm.com/?act=detail&tid=28861

相关文章:

  • 2025新型液压阀块定制厂家推荐,美泰克精密机械匠心打造!
  • commitlint Lint 提交消息格式控制
  • 2025氢氧化镁供应厂家推荐:辽宁润辉新材料科技优质厂家首选
  • 2025年离心曝气机源头工厂哪家强?离心曝气机知名厂家哪家好?
  • 2025整平机厂家最新推荐榜:高效精准与耐用品质的行业首选!
  • 2025黄金回收品牌最新推荐榜:高信誉与专业服务的首选厂家!
  • 2025复合钢丝网优质厂家推荐,昆山佳冠光电科技实力见证!
  • 射流曝气机推荐厂家/优质厂家排名/哪个品牌好?
  • 第七章 验收手写数字识别
  • 2025保洁公司权威推荐:上海恒旺保洁服务,口碑与实力兼备!
  • 初识pytorch:深度学习中关于数据加载的Dataset和DataLoader
  • 中考_学科
  • 2025卧式CNC高压清洗机厂家推荐榜:高效清洁与卓越性能首
  • 2025年深水搅拌机曝气机优质供应商推荐品牌/源头工厂/哪家好?
  • 工具篇-Cursor中接入DeepSeek,只要这三步
  • 2025年中医确有专长培训TOP5榜单:权威认证与实战经验结
  • .NET 记录Amazon上传S3异常问题
  • 求职信 - MKT
  • Linux中tar、zip、gz、rar文件 解压缩归类
  • PostgreSQL多节点部署分布式数据库之Citus
  • 2025气柱袋厂家最新推荐榜:包装防护与性价比之选!
  • java项目CPU爆高问题排查方案
  • 2025实验室净化优质厂家推荐:华锐净化专业定制,洁净空间首
  • 小九源码-springboot051-智能推荐旅游平台 - 实践
  • 2025方钢供应厂家推荐:山东鑫泽金属制品优质选择!
  • 2025年中国行业内领先的GEO(AI搜索优化)厂家权威推荐榜单:四川云视GEO当首
  • 【vLLM】使用vLLM部署Qwen3-VL-30B-A3B-Instruct
  • 2025 屋顶防水维修/外墙防水维修/电梯井防水维修厂家推荐榜:专注全场景渗漏解决方案供应!
  • 2025 流化床/GMP标准/实验室气流粉碎机厂家推荐榜:聚焦多行业粉碎需求,赋能高效生产!
  • 2025年OPP涂布机源头厂家最新推荐榜:技术领先与市场口碑