問題描述
把 1 ∼ 2020 放在 2 × 1010 的矩陣裡。
要求同一行中右邊的比左邊大，同一列中下邊的比上邊的大。一共有多少種方案？
答案很大，你只需要給出方案數除以 2020 的餘數即可。
答案提交
這是一道結果填空題，你只需要算出結果後提交即可。
本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多餘的內容將無法得分。
答案：1340
題解
動態規劃：
f[i][j]
集合：所有第一行有 i 個數位，第二行有 j 個數位的方案的集合屬性：數量決策：
f[i][j] += f[i - 1][j]f[i][j] += f[i][j - 1]#include <iostream>
using namespace std;
int f[1020][1020];
int main()
{
f[0][0] = 1; // 兩行一個數位都不放，也是一種方案
for (int i = 0; i <= 1010; i ++)
for (int j = 0; j <= i && j <= 1010; j ++)
{
if(i - 1 >= j) // 轉移前的狀態也要合法，即第一行的數量不小於第二行的數量
f[i][j] += f[i - 1][j] % 2020;
if(j)
f[i][j] += f[i][j - 1] % 2020;
}
cout << f[1010][1010] << endl;
return 0;
}
ps：發現這道題目來源於《演演算法競賽進階指南》，原題是 【楊老師的照相排列】，只不過是超級弱化版，果然多做題才能長見識 😂