1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

C ( n , m ) = C ( n − 1 , m ) + C ( n − 1 , m − 1 ) C(n,m)=C(n-1,m)+C(n-1,m-1) C(n,m)=C(n−1,m)+C(n−1,m−1)是可以用杨辉三角预处理

C(n,m)%k=(C(n-1,m)+C(n-1,m-1))%k = C(n-1,m)%k + C(n-1,m-1)%k

可以O(nm)预处理C(n,m)能否被k整除

接下来处理二维前缀和

一维： f [ i ] = f [ i − 1 ] + a [ i ] f[i]=f[i-1]+a[i] f[i]=f[i−1]+a[i]

二维： f [ i , j ] = f [ i − 1 , j ] + f [ i , j − 1 ] − f [ i − 1 ] [ j − 1 ] + a [ i , j ] f[i,j]=f[i-1,j]+f[i,j-1]-f[i-1][j-1]+a[i,j] f[i,j]=f[i−1,j]+f[i,j−1]−f[i−1][j−1]+a[i,j]
a [ i , j ] a[i,j] a[i,j]=(C(i,j)%k==0)