萌新蒟蒻，老师在讲状压DP，但是概念没学直接做的题。实在是不会做，求助。

题目如下：

只剩下马了

题目描述

皇后、车、炮、国王……全被考完了，只能考一考马了

问一个 n∗n的棋盘里要放k只马，有多少种不同的方案？

马的规则参考国际象棋，能攻击到8个位置

如下图

OXOXO

XOOOX

OOMOO

XOOOX

OXOXO

M为马的位置，X是能攻击到的位置

输入格式 输入一行两个正整数 n，k。

输出格式 输出一行一个正整数，表示情况总数。答案保证在 二的六十四次方范围内。

最小的分数

题目描述

震惊！一道小学数学题竟然90%的人都做不起！ 12/11<a/b<10/11其中a,b为正整数，求a+b的最小值。

现在题目有所变化，需要你编程解决

给你四个数a1,a2,b1,b2,你需要找一个分数x/y,满足

a1/b1<=x/y<=a2/b2

（注意这里是小于等于，如果把题目变为小于其实也能做，但有更多思考量，推荐你考试后思考）

且x+y最小，请输出这个最小值

一共有多组询问，每组询问你都要输出一行答案

你会得知一个数据规模n，题目中的所有正整数最大不超过n.

输入格式

输入一行一个正整数 n，表示数据规模

之后一行一个正整数q，表示一共有q组询问

之后q行，每行4个正整数a1,a2,b1,b2，

确保全部的数字都不超过n，所有分数都是最简分数，且a1/b1<=a2/b2

输出格式

输出q行，每行一个正整数，表示答案。

错了一行

题目描述

小L有一个数列arr，是1到n的一个全排列，他想用下列算法在不消耗新空间的情况下将数列从小到大排序. for(int i=1; i<=n; i++) while(arr[i] != i) swap(arr[i], arr[arr[i]]);

这个代码既简洁又漂亮，小L高兴极了

但他在写代码时错了一行，变成了：

for(int i=1; i<=n; i++) swap(arr[i], arr[arr[i]]);

最后竟然答案还是对的！

小L想知道，对于所有的长度为n的全排列，其中有多少个全排列是可以在写错代码的时候仍然能成功排序的。

你能帮帮他吗？ 输入格式

输入一行一个正整数 n。

输出格式

输出一行一个正整数，表示情况总数。

由于答案太大，你需要对998244353取模。

画布染色

题目描述

小L有一个 n∗n的白色方格画布，为了让画布变得五颜六色，小L有四个操作

1 col pos ：将 1、2、……、pos列全部染上col色

2 col pos ：将pos、pos+1、……、n列染上col色

3 col pos ：将 1、2、……、pos行全部染上col色

4 col pos ：将pos、pos+1、……、n行染上col色

但是颜色具有消除效应，如果两次对一个格子染同一个颜色，那么相当于没有染色

颜色还有混合效应，也就是说一个格子可能有多个颜色

小L想知道，染完色之后各种颜色的面积.

输入格式

第一行两个正整数 n，cnt，表示画布大小，颜色总数

第二行一个正整数m，表示操作数量

之后m行，每行三个正整数op，col，pos，意义如题目所言.

按照排列组合，应该有2的cnt次方种颜色 种不同的颜色（包括白色）

输出格式

2的cnt次方行，每行一个正整数，表示不同颜色的面积，按照从小到大排列

如果一个颜色不存在，则面积为0