汽车用品东莞网站建设,建筑资料免费下载网站,服装设计网上自学课程,网络营销方案策划实训报告正题
题目链接:https://www.luogu.com.cn/problem/P5664 题目大意
对于nnn个方法#xff0c;mmm个材料#xff0c;一个方法配对一个材料可以做an,ma_{n,m}an,m道菜。选择kkk个配对要求
配对至少为k1k1k1每个配对的方法不同每个材料最多用⌊k2⌋\lfloor\frac…正题
题目链接:https://www.luogu.com.cn/problem/P5664 题目大意
对于nnn个方法mmm个材料一个方法配对一个材料可以做an,ma_{n,m}an,m道菜。选择kkk个配对要求
配对至少为k1k1k1每个配对的方法不同每个材料最多用⌊k2⌋\lfloor\frac{k}{2}\rfloor⌊2k⌋次
求做菜方案数 解题思路
考虑容斥减去多余方案也就是要求一个材料用超过一半。枚举这个超过一半的材料设fi,jf_{i,j}fi,j表示选到第iii个方法这个材料减去其他材料的使用次数为jjj那么这个多余方案的答案就是jjj为正数的fff值。 时间复杂度O(n2m)O(n^2m)O(n2m) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N110,M2100,XJQ998244353;
ll n,m,a[N][M],f[N][2*N],s[N],ans1;
int main()
{scanf(%lld%lld,n,m);for(ll i1;in;i){for(ll j1;jm;j){scanf(%lld,a[i][j]);(s[i]a[i][j])%XJQ;}ansans*(s[i]1)%XJQ;}for(ll k1;km;k){memset(f,0,sizeof(f));f[0][n]1;for(ll i1;in;i)for(ll j0;j2*n;j){f[i][j]f[i-1][j];if(j!2*n)f[i][j](f[i][j]f[i-1][j1]*(s[i]-a[i][k]XJQ)%XJQ)%XJQ;if(j!0)f[i][j](f[i][j]f[i-1][j-1]*a[i][k]%XJQ)%XJQ;}for(ll jn1;j2*n;j)ans(ans-f[n][j]XJQ)%XJQ;}printf(%lld,(ans-1XJQ)%XJQ);
}
