Emiya 家今天的饭

科技前沿 • 2025-02-24 15:08 • 阅读 47

大家好，我是讯享网，很高兴认识大家。

一、题目

点此看题

二、解法

0x01 暴力
可以考虑搜索，时间复杂度 $O(m^n)$ ，可以拿到 $32$ 分的高分。
考虑 $m\leq 3$ 的部分分，直接四维 $d p$ ，定义 $d p [i] [j] [k] [l]$ 为前 $i$ 行分别选 $j, k, l$ 个，转移也不难，时间复杂度 $O(n^4m)$ ，可以拿到 $60$ 分的高分。
0x02 正解
首先有一个显然的想法，先考虑第一个条件，然后再容斥第二个条件，考虑题目给的 $1 / 2$ ，也就意味着我们可以 $全部 - 每种主菜超过 1 / 2 的方案数$ ，易发现这种计算方法不重不漏。
现在就有两种思路，第一种是排列组合的思想，由于给的 $a$ 太恶心，这种方法应该是难做的。既然排列组合做不出来，考虑计数 $d p$ ，我们先枚举钦定的主菜，定义 $d p [i] [j] [k]$ 为在钦定这种主菜的情况下前 $i$ 行中选 $j$ 个，钦定的主菜选了 $k$ 个，转移略。
这样已经能拿到 $84$ 的高分了，如果你有职业精神，那就继续考虑优化，优化主要是要把 $j$ 那一维给优化掉，考虑改变状态定义 $d p [i] [k]$ 为前 $i$ 行的操作权值为 $k$ 的总方案，我们给三种操作赋权值，如果不选，权值为 $1$ ；如果选了其他主菜，权值为 $0$ ；如果选了当前主菜，权值为 $2$ ，可以发现我们最后要求的就是 $\sum dp[n][k]$ ， $(n+1\leq k\leq 2n)$ ，转移如下：（ $s u m$ 是当前行的 $a$ 求和，我们已枚举了主菜 $j$ ）。

讯享网

$\begin{cases} dp[i][k]+=dp[i-1][k]\times (sum[i]-a[i][j]) \\ dp[i][k+1]+=dp[i-1][k] \\ dp[i][k+2]+=dp[i-1][k]\times a[i][j] \end{cases}$

时间复杂度 $O(mn^2)$ 。

#include <cstdio> #include <cstring> #define int long long const int MAXN = 105; const int MAXM = 1005; const int MOD = ; int read() { 
    int x=0,flag=1;char c; while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1; while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=getchar(); return x*flag; } int n,m,a[MAXN][MAXM*2],sum[MAXN]; int ans=1,dp[MAXN][MAXN*2]; signed main() { 
    n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { 
    a[i][j]=read(); sum[i]+=a[i][j]; sum[i]%=MOD; } for(int i=1;i<=n;i++) ans*=(sum[i]+1),ans%=MOD; ans--; for(int j=1;j<=m;j++) { 
    for(int i=0;i<=n;i++) for(int k=0;k<=2*n;k++) dp[i][k]=0; dp[0][0]=1; for(int i=1;i<=n;i++) for(int k=0;k<=2*n;k++) { 
    dp[i][k]+=dp[i-1][k]*(sum[i]-a[i][j]),dp[i][k]%=MOD; dp[i][k+1]+=dp[i-1][k],dp[i][k+1]%=MOD; dp[i][k+2]+=dp[i-1][k]*a[i][j],dp[i][k+2]%=MOD; } for(int i=n+1;i<=2*n;i++) ans-=dp[n][i],ans%=MOD; } printf("%lld\n",(ans%MOD+MOD)%MOD); }

讯享网

Emiya 家今天的饭

一、题目

二、解法

相关推荐