此题n的范围比较小
可以考虑直接暴搜
但是这里我们考虑组合数做法

我们考虑除了 $n * n==k$ 的情况外
我们选择不同的$xy$造成的最终情况是不同的
我们枚举要选多少个$x$
假设我们选择了$i$个$x$
每个$x$会占用$n$个格子
那么我们还剩下$k - n * i$的格子用来选$y$
由于已经选了$i$个$x$
那么现在再选y会增加n-i个格子被涂色
那么需要选 $(k-n*i)/(n-i)$个$y$
调用组合数 统计答案
若提前预处理组合数的阶乘
时间复杂度可以达到$O(n)$

class Solution {
public:
    int C(int a,int b){
        if(b>a) return 0;
        int ans=1;
        for(int i=a;i>a-b;i--)
            ans*=i;
        for(int i=1;i<=b;i++)
            ans/=i;
        return ans;
    }
    int paintingPlan(int n, int k) {
        if(n*n==k)return 1;
        int ans=0;
        for(int i=0;i<=n;i++)//x涂i个 
        {
            int tot=(k-i*n);//涂y轴还要涂多少
            if(tot>=0&&tot%(n-i)==0){
                ans+=C(n,i)*C(n,tot/(n-i));
            } 
        }
        return ans;
    }
};