思路

  • 暴力搜索加剪枝
  • 搜索过程中行或者列的和大于sum剪掉
  • 搜索到(x,y)，假设剩下的都取最大值sum，能否满足要求，如果不能剪掉
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 1e3 + 10, M = N * 2;
const int INF = 0x3f3f3f3f3f3f3f3f;
int a[N][N];
int srow[N], scol[N];
int res, n, sum, cnt;
void dfs(int x, int y)
{
    if(y == n)
    {
        x ++;
        y = 0;
    }
    if(x == n)
    {
        //cout << cnt << endl;
        int ff = 0;
        for(int i = 0; i < n; i ++)
        {
            //cout << srow[i] << ' ';
            if(srow[i] != sum || scol[i] != sum)
            {
                ff = 1;
                 break;
            }
        }
        //cout << endl;
        if(ff == 0) res ++;
        return ;
    }
    for(int i = 0; i <= sum; i ++)
    {
        a[x][y] = i;
        if(srow[x] + i > sum || scol[y] + i > sum) continue ;
        if(srow[x] + i + (n - y - 1) * sum < sum || scol[y] + i + (n - x - 1) * sum < sum) continue;
        srow[x] += i;
        scol[y] += i;
        dfs(x, y + 1);
        srow[x] -= i;
        scol[y] -= i;
    }
}
signed main()
{
    cin >> sum >> n;
    dfs(0, 0);
    cout << res << endl;
    //cout << cnt << endl;
    //cout << (int)pow(8, 9) << endl;
    return 0;
}