洛谷P3941 入阵曲

用$sum\left [ i \right ]\left [ j \right ]$，记录第i 行，前j 个的和
枚举i ,j 两列$\left ( i<j \right ) ​$，用数组$c\left [ k \right ] ​$记录$sum\left [ k \right ]\left [j \right ]-sum\left [ k \right ]\left [ i-1 \right ] ​$
对于c 求一遍前缀和记为s，当且仅当$s\left [ i -1\right ]\equiv s\left [ j \right ]\left ( mod \ M \right )$，$\left [ i,j \right ]mod\ M=0$
用$cnt\left [ p \right ]$记录$s\equiv p\left ( mod \ M \right )$的个数，从左往右扫一遍
要注意的是$cnt\left [ 0 \right ]=1$
但是以上操作没有考虑仅一列的情况，枚举每一列再重复一遍以上操作

#include<cstdio>
#include<vector>
#define LL long long
using namespace std;
const int N=405,M=1000050;
int w[N][N],cnt[M],c[N],n,m,mod,sum[N][N];
LL ans=0;
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
int main()
{
    n=read(),m=read(),mod=read(),cnt[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) w[i][j]=read()%mod;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            sum[i][j]=(sum[i][j-1]+w[i][j])%mod;
    for(int i=1;i<=m;i++)
        for(int j=i+1;j<=m;j++)
        {
            for(int k=1;k<=n;k++)
                c[k]=(sum[k][j]-sum[k][i-1]+mod)%mod;
            for(int k=1;k<=n;k++)
            {
                c[k]=(c[k-1]+c[k])%mod;
                ans+=cnt[c[k]],cnt[c[k]]++;
            }
            for(int k=1;k<=n;k++) cnt[c[k]]--;		
        }
    for(int i=1;i<=m;i++)
    {
        for(int k=1;k<=n;k++) c[k]=w[k][i];
        for(int k=1;k<=n;k++)
        {
            c[k]=(c[k-1]+c[k])%mod;
            ans+=cnt[c[k]],cnt[c[k]]++;
        }
        for(int k=1;k<=n;k++) cnt[c[k]]--;
    }
    printf("%lld",ans);
    return 0;
}