数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序查找包含最小和最大元素的序列对
假设我们有三个数字N、M和K。有N行和M列。我们将在每个单元格中写入1到K之间的整数，并定义序列A和B，使得 -
对于从1到N的每个i，A[i]是第i行的所有元素的最小值
对于从1到M的每个j，B[j]是第j列的所有元素的最大值
我们必须找到(A, B)的对数。如果答案过大，则返回结果模998244353。
因此，如果输入类似于N = 2；M = 2；K = 2，则输出将为7，因为(A[1]，A[2]，B[1]，B[2])为(1,1,1,1)、(1,1,1,2)、(1,1,2,1)、(1,1,2,2)、(1,2,2,2)、(2,1,2,2)或(2,2,2,2)。
步骤
为了解决这个问题，我们将遵循以下步骤 -
p := 998244353 Define a function power(), this will take a, b, and return (a^b) mod p From the main method, do the following: if n is same as 1, then: return power(K, m) if m is same as 1, then: return power(K, n) ans := 0 for initialize t := 1, when t <= K, update (increase t by 1), do: ans := (ans + (power(t, n) - power(t - 1, n) + p) mod p * power(K - t + 1, m)) mod p return ans
示例
让我们看看以下实现以获得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
long p = 998244353;
long power(long a, long b, long ret = 1){
for (; b; b >>= 1, a = a * a % p)
if (b & 1)
ret = ret * a % p;
return ret;
}
long solve(int n, int m, int K){
if (n == 1)
return power(K, m);
if (m == 1)
return power(K, n);
long ans = 0;
for (long t = 1; t <= K; t++){
ans = (ans + (power(t, n) - power(t - 1, n) + p) % p * power(K - t + 1, m)) % p;
}
return ans;
}
int main(){
int N = 2;
int M = 2;
int K = 2;
cout << solve(N, M, K) << endl;
}输入
2, 2, 2
输出
7
更新于: 2022年3月2日
287 次查看
广告