原题如下:
把 1 ∼ 2020 放在 2 × 1010 的矩阵里。要求同一行中右边的数字比左边数字大,同一列中下边的数字比上边的数字大。一共有多少种方案?
答案很大,你只需要给出方案数除以 2020 的余数即可。
- 当第一行数字个数==第二行数字个数,说明最新的数加在了第二行,结果会与同等第一行数字但第二行数字个数-1的情况相同。
- 当第一行数字个数>第二行数字个数,说明可能是最新数字加在第一行或者第二行,都符合规则就加一起。
- 若第一行数字个数<第二行数字个数,非法,违反了题意直接毙掉。
#include <iostream>
using namespace std;
const int N = 1011;
int f[N][N];//i为第一行的个数 j为第二行的数字个数
int main()
{
for(int i=1; i<=1010; i++){
f[i][0] = 1;
for(int j=1; j<=1010; j++){
if(i == j) f[i][j] = f[i][j-1] % 2020;
else if(i > j) f[i][j] = (f[i-1][j] + f[i][j-1]) % 2020;
else break;
}
}
cout<<f[1010][1010]<<endl;
return 0;
}
蹲个眼,明天补一下这题,感觉跟我想的状态不一样