資料結構
網路
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 次檢視
廣告