2018-div-matrix

由题意知：a[i][j] % a[i -1][j] == 0 && a[i][j] % a[i][j - 1] == 0根据这个条件可以dfs

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i = a; i <= b; i++)
typedef long long ll;
const int mod = 1e9 + 7;
int dp[4] = {1,2,1009,2018};
int a[2100][2100],n,m,ans;

void dfs(int x,int y){
    if(x == n + 1){
      //  For(i,1,n) {
        //    For(j, 1, m) cout << a[i][j] << " ";
        //    cout << endl;
       // }
        ans++;
    }else{
        if(x == 1){
            For(i,0,3){
                if(a[x][y - 1] % dp[i] == 0 && !a[x][y]){
                    a[x][y] = dp[i];
                    if(y != m) dfs(x,y + 1);
                    else dfs(x + 1,1);
                    a[x][y] = 0;
                }
            }
        }else if(y == 1){
            For(i,0,3) {
                if (a[x - 1][y] % dp[i] == 0 && !a[x][y]){
                    a[x][y] = dp[i];
                    if(y != m) dfs(x,y + 1);
                    else dfs(x + 1,1);
                    a[x][y] = 0;
                }
            }
        }else if(x <= n && y <= m){
            For(i,0,3){
                if(a[x - 1][y] % dp[i] == 0 && a[x][y - 1] % dp[i] == 0 && !a[x][y]){
                    a[x][y] = dp[i];
                    if(y != m) dfs(x,y + 1);
                    else dfs(x + 1,1);
                    a[x][y] = 0;
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    while(cin >> n >> m) {
        ans = 0;
        memset(a,0,sizeof(a));
        a[1][1] = 2018;
        dfs(1, 2);
        cout << ans << endl;
    }
}

View Code

得到：

行列	1	2	3	4	5
1	1	4	9	16	25
2	4	25	81	196	400
3	9	81	361	1156	3025
4	16	196	1156	4761	15625
5	25	400	3025	15625	63001

方案数上： dp[i][j] = dp[j][i] 除此之外，每个数都是平方数，那规律是不是在这里？

行列	1	2	3	4	5
1	1²	2²	3²	4²	5²
2	2²	5²	9²	14²	20²
3	3²	9²	19²	34²	55²
4	4²	14²	34²	69²	125²
5	5²	20²	55²	125²	251²

原题中说a[i][j]和a[i -1][j],a[i][j- 1]有关系,由此得到：dp[i][j] = (√dp[i -1][j] + √dp[i][j -1] + 1)²

为了进一步简化代码，dp[i][j]的平方代表最后答案，也就是dp[i][j]是根号下的数字

综上 dp[i][j] = dp[i][j -1] + dp[i - 1][j] + 1; ans = pow( dp[i]pj] )

代码

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i = a; i <= b; i++)
#define int long long
const int mod = 1e9 + 7;
const int maxn = 2e3 + 10;
int dp[maxn][maxn],n,m;
signed main(){
    ios::sync_with_stdio(0);
    For(i,1,2000) dp[1][i] = dp[i][1] = i;
    For(i,2,2000) For(j,2,2000)
    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] + 1) % mod;
    while(cin >> n >> m)
        cout << dp[n][m] * dp[n][m] % mod << endl;
    return 0;
}

View Code