题解：P1771 方程的解

· · 题解

数据范围这么小，为什么没有 dp 呢？

直接设 f_{i,j} 为考虑到第 i 个数，前面数的和为 j。

转移很显然：

f_{i,j}=\displaystyle\sum_{p=i-1}^{j-1}f_{i-1,p}

直接枚举 i,j,k 是 O(n^3) 的，但是发现后面的式子是一段前缀，可以前缀和优化。于是记 s_{i,j}=\displaystyle\sum_{p=0}^{j-1}f_{i,p}，那么 f_{i,j}=s_{i-1,j-1}。

发现是杨辉三角，但我们的复杂度已经够优秀了。

人生苦短，我用 python

def qpow(x=0,y=0):
    res=1
    while y!=0:
        if y&1:
            res=res*x%1000
        x=x*x%1000
        y>>=1
    return res
def main():
    k,x=map(int,input().split())
    f=[[0 for i in range(1002)]for i in range(k+2)]
    x=qpow(x,x)
    f[0][0]=1
    for i in range(1,k+1):
        tmp=0
        for j in range(0,x+1):
            f[i][j]+=tmp
            tmp+=f[i-1][j]
    print(f[k][x])
if __name__ == "__main__":
    main()