首页 › 题库 › 信息学奥赛 › 5.1 素数与筛法

信息学奥赛-提高级 题库

共 2 道题 · 按题型筛选,点「查看答案」核对解析
章节 5.1 素数与筛法 清除
1 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.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。

答案与解析
参考答案

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#define mod 998244353

 

using namespace std;

typedef long long ll;

const int MAXN = 105, MAXM = 2005;

int n,m,a[MAXN][MAXM],sum[MAXN][MAXM];

ll f[MAXN][MAXN*2],g[MAXN][MAXN];

 

int main()

{

cin >> n >> m;

for(int i = 1; i<=n; i++)

    for(int j = 1; j<=m; j++)

    {

        scanf("%d",&a[i][j]);

        sum[i][0] = (sum[i][0]+a[i][j])%mod;

}

    for(int i = 1; i<=n; i++)

        for(int j = 1; j<=m; j++)

            sum[i][j] = (sum[i][0]-a[i][j]+mod)%mod;

    ll ans = 0;

    for(int col = 1; col<=m; col++)

    {

        memset(f,0,sizeof(f));

        f[0][n] = 1;

        for(int i = 1; i<=n; i++)

            for(int j = n-i; j<=n+i; j++) 

                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;

        for(int j = 1; j<=n; j++)

            ans = (ans+f[n][n+j])%mod;

}

g[0][0] = 1;

for(int i = 1; i<=n; i++)

    for(int j = 0; j<=n; j++) 

    g[i][j] = (g[i-1][j]+(j>0?g[i-1][j-1]*sum[i][0]%mod:0))%mod;

    for(int j = 1; j<=n; j++)

    ans = (ans-g[n][j]+mod)%mod;  

cout << ans*(mod-1)%mod << endl;

return 0;

}

题目详情
2 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.1 素数与筛法

笨小猴

【问题描述】

笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!

这种方法的具体描述如下:假设 maxn 是单词中出现次数最多的字母的出现次数,minn是单词中出现次数最少的字母的出现次数,如果 maxn-minn 是一个质数,那么笨小猴就认为这是个 Lucky Word,这样的单词很可能就是正确的答案。

【输入】

输入文件 word.in 只有一行,是一个单词,其中只可能出现小写字母,并且长度小于 100。

【输出】

输出文件 word.out 共两行,第一行是一个字符串,假设输入的的单词是 Lucky Word,那么输出“Lucky Word”,否则输出“No Answer”;

第二行是一个整数,如果输入单词是 Lucky Word,输出 maxn-minn 的值,否则输出 0。 

【输入输出样例 1】

【输入输出样例 1 解释】

单词 error 中出现最多的字母 r 出现了 3 次,出现次数最少的字母出现了 1 次,3-1=2,2 是质数。

【输入输出样例 2】

【输入输出样例 2 解释】

单词 olympic 中出现最多的字母 i 出现了 2 次,出现次数最少的字母出现了 1 次,2-1=1,1不是质数。

答案与解析
参考答案

#include<bits/stdc++.h>  //万能头文件

using namespace std;

int primenum(int m);  //质数的判断

int main()

{

char ch[1000];

int array[100]={0};

int m,n,i,j,k;

int maxn=-500,minn=9999;

scanf("%s",ch);

for(int m=0;m<strlen(ch);m++){

array[ch[m]-'a']++;

}

for(int m=0;m<26;m++){

if(array[m]>maxn&&array[m]!=0) maxn=array[m];

if(array[m]<minn&&array[m]!=0) minn=array[m];

}

if(primenum(maxn-minn)){

printf("Lucky Word\n%d",maxn-minn);

}else{

printf("No Answer\n0");

}

}

int primenum(int m)

{

int i;

if(m==2||m==3) return 1;

if(m==1||m==0) return 0;

if(m%6!=1&&m%6!=5) return 0;  //优化质数的判断方法

for(i=5;i<=sqrt(m);i+=5){

if(m%i==0||m%(i+2)==0){

return 0;

}

题目详情