简答题 偏难
#23310

Emiya家今天的饭 【题目描述】 Emiya 是个擅长做菜的高中生,他共掌握 n 种烹饪方法,且会使用 m 种主要食材做菜。为了方便叙述,我们对烹饪方法从 1…

Emiya家今天的饭

【题目描述】

Emiya 是个擅长做菜的高中生,他共掌握 n 种烹饪方法,且会使用 m 种主要食材做菜。为了方便叙述,我们对烹饪方法从 1~n 编号,对主要食材从 1 ~m 编号。

Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地,Emiya 会做 ai,j 道不同的使用烹饪方法 i 和主要食材 j 的菜(1 ≤i≤n,1≤j≤m),这也意味着 Emiya 总共会做

道不同的菜。

Emiya 今天要准备一桌饭招待 Yazid 和 Rin 这对好朋友,然而三个人对菜的搭配有不同的要求,更具体地,对于一种包含 k 道菜的搭配方案而言:

(1)Emiya 不会让大家饿肚子,所以将做至少一道菜,即 k≥1

(2)Rin 希望品尝不同烹饪方法做出的菜,因此她要求每道菜的烹饪方法互不相同

(3)Yazid 不希望品尝太多同一食材做出的菜,因此他要求每种主要食材至多在一半的菜(即道菜)中被使用

这里的⌊x⌋ 为下取整函数,表示不超过 x 的最大整数。

这些要求难不倒 Emiya,但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同,当且仅当存在至少一道菜在一种方案中出现,而不在另一种方案中出现。

Emiya 找到了你,请你帮他计算,你只需要告诉他符合所有要求的搭配方案数对质数998,244,353 取模的结果。

【输入格式】

从文件meal.in中读入数据。

第 1 行两个用单个空格隔开的整数 n,m。

第 2 行至第 n+1 行,每行 m 个用单个空格隔开的整数,其中第 i + 1行的 m 个数依次为 ai,1,ai,2,⋯,ai,m。

【输出格式】

输出到文件meal.out中。

仅一行一个整数,表示所求方案数对 998,244,353 取模的结果。

【样例 1 输入】

2 3 

1 0 1

0 1 1

【样例 1 输出】

3

【样例1解释】

由于在这个样例中,对于每组i,j,Emiya都最多只会做一道菜,因此我们直接通 过给出烹饪方法、主要食材的编号来描述一道菜。

符合要求的方案包括:

•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材2的菜

•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材3的菜

•做一道用烹饪方法1、主要食材3的菜和一道用烹饪方法2、主要食材2的菜

 因此输出结果为3 mod 998,244,353 = 3。

需要注意的是,所有只包含一道菜的方案都是不符合要求的,因为唯一的主要食材 在超过一半的菜中出现,这不满足Yazid的要求。

【样例2输入】

3 3

1 2 3

4 5 0

6 0 0

【样例2输出】

190

【样例2解释】

Emiya必须至少做2道菜。

做2道菜的符合要求的方案数为100。

做3道菜的符合要求的方案数为90。

因此符合要求的方案数为100 + 90 = 190。

【样例3输入】

5 5

1 0 0 1 1

0 1 0 1 0

1 1 1 1 0

1 0 1 0 1

0 1 1 0 1

【样例3输出】

742

【数据范围】

对于所有测试点,保证 1 ≤n≤ 100, 1 ≤ m ≤ 2000, 0≤ai,j< 998,244,353。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p style="text-align: left;">#include &lt;iostream&gt;</p><p style="text-align: left;">#include &lt;cstdlib&gt;</p><p style="text-align: left;">#include &lt;cstring&gt;</p><p style="text-align: left;">#include &lt;cstdio&gt;</p><p style="text-align: left;">#define mod 998244353</p><p> </p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">typedef long long ll;</p><p style="text-align: left;">const int MAXN = 105, MAXM = 2005;</p><p style="text-align: left;">int n,m,a[MAXN][MAXM],sum[MAXN][MAXM];</p><p style="text-align: left;">ll f[MAXN][MAXN*2],g[MAXN][MAXN];</p><p> </p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>cin &gt;&gt; n &gt;&gt; m;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1; i&lt;=n; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>    for(int j = 1; j&lt;=m; j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>    {</p><p style="text-align: left;"><span style="white-space:pre"> </span>        scanf("%d",&amp;a[i][j]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>        sum[i][0] = (sum[i][0]+a[i][j])%mod;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">    for(int i = 1; i&lt;=n; i++)</p><p style="text-align: left;">        for(int j = 1; j&lt;=m; j++)</p><p style="text-align: left;">            sum[i][j] = (sum[i][0]-a[i][j]+mod)%mod;</p><p style="text-align: left;">    ll ans = 0;</p><p style="text-align: left;">    for(int col = 1; col&lt;=m; col++)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        memset(f,0,sizeof(f));</p><p style="text-align: left;">        f[0][n] = 1;</p><p style="text-align: left;">        for(int i = 1; i&lt;=n; i++)</p><p style="text-align: left;">            for(int j = n-i; j&lt;=n+i; j++) </p><p style="text-align: left;">                f[i][j] = (f[i-1][j]+f[i-1][j-1]*a[i][col]%mod+f[i-1][j+1]*sum[i][col]%mod)%mod;</p><p style="text-align: left;">        for(int j = 1; j&lt;=n; j++)</p><p style="text-align: left;">            ans = (ans+f[n][n+j])%mod;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>g[0][0] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1; i&lt;=n; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>    for(int j = 0; j&lt;=n; j++) </p><p style="text-align: left;"><span style="white-space:pre"> </span>    g[i][j] = (g[i-1][j]+(j&gt;0?g[i-1][j-1]*sum[i][0]%mod:0))%mod;</p><p style="text-align: left;">    for(int j = 1; j&lt;=n; j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>    ans = (ans-g[n][j]+mod)%mod;  </p><p style="text-align: left;"><span style="white-space:pre"> </span>cout &lt;&lt; ans*(mod-1)%mod &lt;&lt; endl;</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。