2018-div-matrix

NC52483. 2018-div-matrix

描述

Bobo 想统计满足下面条件的矩阵 A 的数量。
1. 矩阵 A 有 n 行 m 列，每个元素都是正整数。第 i 行第 j 列的元素用 $A_{i, j}$ 表示。
2. $A_{1, 1} = 2018$ .
3. 对于所有 $2 \leq i \leq n, 1 \leq j \leq m$ ， $A_{i, j}$ 是 $A_{i - 1, j}$ 的约数。
4. 对于所有 $1 \leq i \leq n, 2 \leq j \leq m$ ， $A_{i, j}$ 是 $A_{i, j - 1}$ 的约数。
因为满足条件的矩阵 A 数量很多，Bobo 只想统计满足条件的矩阵数量除以 $(10^9+7)$ 的余数。

输入描述

输入文件包含多组数据，请处理到文件结束。
每组数据包含 2 个整数 n 和 m.

输出描述

对于每组数据输出 1 个整数表示所求的数量除以  的余数。

示例1

输入:

输出:

说明:

对于第二组样例(n = 1, m = 2)，满足条件的矩阵 A 有 (2018, 2018), (2018, 1009), (2018, 2), (2018, 1) 共 4 种。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 262ms, 内存消耗: 32740K, 提交时间: 2019-10-03 16:14:22

#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e9+7;
ll a[2001][2001];
int main(){
	int n,m;
	for(int i=1;i<=2000;i++){
		for(int j=1;j<=2000;j++){
			a[i][j] = (a[i-1][j]+a[i][j-1]+1)%maxn;
		}
	}
	while(cin>>n>>m){
		cout<<(a[n][m]*a[n][m])%maxn<<endl;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 82ms, 内存消耗: 17020K, 提交时间: 2019-10-03 15:43:22

#include <cstdio>
int f[2010][2010],n,m;
int main(){
	for(int i=1;i<=2000;++i)for(int j=1;j<=2000;++j)f[i][j]=(f[i-1][j]+f[i][j-1]+1)%1000000007;
	while(scanf("%d%d",&n,&m)!=EOF)printf("%d\n",(1ll*f[n][m]*f[n][m])%1000000007);
	return 0;
}