腾讯益智小游戏"/>
腾讯益智小游戏
腾讯游戏开发了一款全新的编程类益智小游戏,榜首的题目是一道关于矩阵的计算,你用多久能计算出来呢?
游戏中给出一个 N \times MN×M 的矩阵,若其中填入的内容是数字 1 \sim N \times M1∼N×M 的排列,求问有多少种不等价的矩阵?
等价矩阵:若一个矩阵 AA 可以通过交换其中两行或者两列变成另一个矩阵 BB,则称 AA 和 BB 等价。且若 AA 和 BB等价,BB 和 CC 等价,则 AA 和 CC 也等价。
答案对 998244353998244353 取模。
说明:
当你计算一个答案需要对某大质数取模的问题时,加减乘都是可以中途取模的,例如 (A+B+C)\%mod(A+B+C)%mod 可以改为 ((A+B)\%mod+C)\%mod((A+B)%mod+C)%mod,这样可以防止运算溢出,而结果不变,注意,当你需要计算除法时,譬如计算 (A/B)\%mod(A/B)%mod,也许 AA 和 BB 本身很大很大,但是经过取模后变成一个相对较小的数,这里再这么算是不对的,比如 mod=7mod=7 时,30/1030/10 的结果本来是 33,但是 AA 和 BB 对 77 取模后变成了 2/32/3,直接计算得到 00,就产生了错误,你可以使用下面的代码中 invinv 函数,当你需要计算 A/B\%modA/B%mod 时可以改写成 (A\%mod)*inv(B \% mod)\%mod(A%mod)∗inv(B%mod)%mod,前提是 BB 不为 00(在模 modmod 后不为 00),注意数据溢出问题,你可能需要使用 long long 类型。inv 函数的复杂度为 \mathcal{O}(\log mod)O(logmod)。
long long inv(long long x) {long long b = mod - 2, ans = 1;while(b) {if(b & 1) {ans = ans * x % mod;}x = x * x % mod;b >>=1;}return ans;
}
输入格式
一行两个正整数 NN 和 MM,空格隔开。
输出格式
一个正整数,表示答案对 998244353998244353 取模的结果。
数据规模
N,M \le 2000N,M≤2000
样例输入1复制
1 2
样例输出1复制
1
样例输入2复制
2 2
样例输出2复制
6
样例输入3复制
3 3
样例输出3复制
10080
做法是:n*m的全排(阶乘)除以 (n的全排*m的全排)
注意应用题目中的函数方法
#include <iostream>
using namespace std;
const int mod = 998244353;long long inv(long long x){ //题目中说的:需要对某大质数取模的问题,相除问题可以//当你需要计算 A/B\%modA/B%mod 时可以改写成 (A\%mod)*inv(B \% mod)\%mod(A%mod)∗inv(B%mod)%mod,//前提是 BB 不为 00(在模 modmod 后不为 00)long long b = mod - 2,ans = 1;while(b){if(b&1) ans = ans*x%mod;x = x*x%mod;b>>=1;}return ans;
}int solve(int a){long long ans = 1;for(int i = 2;i<=a;i++){ //阶乘 全排ans*=i;ans%=mod;}return ans;
}int main(){int n,m;cin >> n >> m;long long x = solve(n*m);long long n1 = solve(n);long long n2 = solve(m);long long y = n1*n2%mod;//cout<<x<<endl;//cout<<y<<endl;//cout<<inv(y)<<endl;cout << (x)*inv(y)%mod << endl; //应用inv函数
}
更多推荐
腾讯益智小游戏
发布评论