美团算法题（技术类）

前言：

据我了解，美团笔试的算法题是比较简单的，大家要查漏补缺，尽量全部做出来，不然可能很难拿到面试（如果题目简单的话）。

ab串

时间限制: 2000/1000 MS (Java/Others)

内存限制: 65536/65536 K (Java/Others)

问题描述

小美数学很好，小团数学不怎么好。有一天小美又在用数学题欺负小团，她提出了这样一个问题：“有多少个长度为n的仅由a和b组成的字符串既不包含aba也不包含bab？如果你算不来大数你可以告诉我这个问题的答案模上998244353是多少”小团实在忍不住了，所以他决定来找你帮忙。

输入描述

第一行有一个整数n(1<=n<=100000)，代表小美问题中的参数。

输出描述

输出一个整数，即小美所问问题的答案除以998244353所得余数。

输入样例1

3

输出样例1

6

----------------------------------------------------

坐公交

时间限制: 2000/1000 MS (Java/Others)

内存限制: 65536/65536 K (Java/Others)

问题描述

小美想坐公交去找小团玩。美团市中共有n个公交站，编号为1到n。同时也有m条公交线路，编号为1到m。小美想知道对于每一对公交站(i,j)从编号为i的站坐公交到编号为j的站至少需要乘坐几条不同的公交线路。

输入描述

第一行有两个整数n,m(1<=n<=500,1<=m<=500,1<=n+m<=500)，代表公交站的个数和公交线路的条数。

接下来n行，每一行开头有一个整数k(1<=k<=m)，代表从这个站可以乘坐k条不同的公交线路。接下来有k个整数，代表这k条公交线路的编号。

输出描述

输出一个n×n的矩阵，矩阵中第i行第j列的数代表从编号为i的站做到编号为j的站至少需要乘坐多少条不同的公交线路。矩阵中每行中的元素由单个空格隔开，且行末不能有空格。

输入样例1

3 2

1 1

2 1 2

1 2

输出样例1

0 1 2

1 0 1

2 1 0