传送门
f[i][j]f[i][j]f[i][j]表示后iii个对答案贡献有jjj个a的方案数。
可以发现最后a,ba,ba,b的总个数一定是n∗(n−1)/2n*(n-1)/2n∗(n−1)/2
因此直接转移就行了。
f[i][j]=f[i+1][j]+f[i+1][j−i]f[i][j]=f[i+1][j]+f[i+1][j-i]f[i][j]=f[i+1][j]+f[i+1][j−i]
解释：要么当前不选，要么选了就会有iii个aaa的贡献。
发现空间有点大？滚动数组优化
代码