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

Combinatorics

[ICPC 2024 Nanjing R] Bingo

先给序列排序,权值相同的钦定标号前的更小。转化成 \(Ans\le a_k\) 的情况,等价于 \(k\)\(1\)\(nm-k\)\(0\) 放入 \(n\times m\) 的矩阵,至少有一行或者一列是全 \(1\)。考虑其反面,钦定共 \(i\)\(j\) 列都是 \(1\) 然后容斥,那么有:

\[f(k)=k!(nm-k)!\sum_{i=0}^n\sum_{j=0}^m(-1)^{i+j}\binom ni\binom mj\binom{nm-nj-im+ij}{k-nj-im+ij} \]

\(s=nj+im-ij\),则 \(\binom{nm-nj-im+ij}{k-nj-im+ij}=\binom{nm-s}{k-s}=(nm-s)!/\left((k-s)!(nm-k)!\right)\)

\(g(s)=\sum_{i=0}^n\sum_{j=0}^m(-1)^{i+j}\binom ni\binom mj(nm-s)!\)\(h(s)=1/s!\),那么 \(f(k)=k!\sum_s g(s)h(k-s)\),卷积即可求出所有的 \(f(k)\),答案即:

\[\sum_{i=1}^{nm}(f(i)-f(i-1))a_i \]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline int read()
{int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x*f;
}
const int N=8e5+10,mod=998244353,G=3,I=332748118,maxn=2e5;
void Add(int &x,int y){x+=y;if(x>=mod)x-=mod;}
void Sub(int &x,int y){x-=y;if(x<0)x+=mod;}
int qpow(int a,int n)
{int ans=1;while(n){if(n&1)ans=1ll*a*ans%mod;a=1ll*a*a%mod;n>>=1; }return ans;
}
namespace poly
{int r[N];void ntt(vector<int> &a,int lim,int k){for(int i=0;i<lim;i++)if(i<r[i])swap(a[i],a[r[i]]);for(int mid=1;mid<lim;mid<<=1){int wn=qpow(k?G:I,(mod-1)/(mid<<1));for(int R=mid<<1,j=0;j<lim;j+=R){int w=1;for(int t=0;t<mid;t++,w=1ll*w*wn%mod){int x=a[j+t],y=1ll*w*a[j+mid+t]%mod;a[j+t]=(x+y)%mod,a[j+mid+t]=(x-y+mod)%mod;}}}}vector<int> mul(vector<int> f,vector<int> g){int n=f.size()-1,m=g.size()-1,lim=1,l=0;while(lim<=n+m)lim<<=1,l++;for(int i=0;i<lim;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));f.resize(lim),g.resize(lim);ntt(f,lim,1),ntt(g,lim,1);vector<int> h(lim);for(int i=0;i<lim;i++)h[i]=1ll*f[i]*g[i]%mod;ntt(h,lim,0);int inv=qpow(lim,mod-2);for(int i=0;i<=lim;i++)h[i]=1ll*h[i]*inv%mod;while(!h.empty()){if(!*--h.end())h.pop_back();else break;}return h;}
}
using poly::mul;
int a[N],g[N],fac[N],ifac[N];
int binom(int n,int m){return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
void sol()
{int n=read(),m=read();for(int i=1;i<=n*m;i++)a[i]=read();sort(a+1,a+n*m+1);vector<int> f(n*m+1),g(n*m+1);for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){int s=n*j+i*m-i*j;if((i+j)&1)Sub(g[s],1ll*binom(n,i)*binom(m,j)%mod*fac[n*m-s]%mod);else Add(g[s],1ll*binom(n,i)*binom(m,j)%mod*fac[n*m-s]%mod);}for(int i=0;i<=n*m;i++)f[i]=ifac[i];f=mul(f,g);for(int i=0;i<=n*m;i++)f[i]=1ll*f[i]*ifac[n*m-i]%mod*fac[i]%mod*fac[n*m-i]%mod;for(int i=0;i<=n*m;i++)f[i]=(fac[n*m]-f[i]+mod)%mod;for(int i=n*m;i>=1;i--)Sub(f[i],f[i-1]); int Ans=0;for(int i=1;i<=n*m;i++)Add(Ans,1ll*f[i]*a[i]%mod);printf("%d\n",Ans);
}
int main()
{fac[0]=1;for(int i=1;i<=maxn;i++)fac[i]=1ll*fac[i-1]*i%mod;ifac[maxn]=qpow(fac[maxn],mod-2);for(int i=maxn-1;i>=0;i--)ifac[i]=1ll*(i+1)*ifac[i+1]%mod; int T=read();while(T--)sol();return 0;
}
http://www.hskmm.com/?act=detail&tid=19438

相关文章:

  • 绘制倒杨辉三角形
  • ABC425 总结
  • 解决方案 | 无需安装任何插件,chrome如何快速搜索书签
  • 订单模块逐字稿
  • 课后作业小结
  • 课后3
  • 尝试决定
  • 竞赛第一步----进实验室
  • Java语法基础课程动手动脑与实验问题深度解析
  • lc1038-从二叉搜索树到更大和树
  • 课程中的问题
  • 课后2
  • Java语法基础课程“动手动脑”问题与实验整理
  • 课后感想
  • mysql的单表如何仅保留半年的数据
  • Java基础核心问题 链接版
  • java作业
  • Insightly存储型XSS漏洞分析:通过链接名称注入恶意脚本
  • H3C交换机的配置学习-01
  • Python脚本生成包含标准的#ifndef保护宏的头文件
  • java实验作业和动手动脑
  • (第三次)Numpy Pandas
  • sg.帮我写一个类似于vb6窗体设计的PySimpleGUI布局设计助手
  • ABC325EF 题解
  • Win11 安装 Python
  • mysql的单表多大要考虑分库分表
  • 2025 采购传感器不踩坑!国内传感器优秀厂家清单:解决精度,防爆,极端环境难题
  • sg.有没有一个可视化辅助设计pysimplegui布局的小工具?
  • 无刷电机速度闭环控制
  • sg.如何使用PySimpleGUI调试器实时监控变量