题解 P3941 入阵曲

题解

观察数据范围，可以 \(\mathcal O(n^2m^2)\) 暴力计算，而加上特殊性质，则可以骗到 \(75pts\)

正解：

我们发现，在一维情况下，\(\mod k\) 相同的前缀和相减，一定是 \(k\) 的倍数。那么我们就可以统计一个不同 \(\mod k\) 的值出现了几次，\(\mathcal O(n)\) 求解。

扩展到二维，做法是将一段连续的行合并成一行，ppt 上叫压行。再按一行的做法做，复杂度 \(\mathcal O(n^2m)\)

注意：记得开 long long，同时记录余数的数组清空时不要用 \(memset\)

Code:

#include<bits/stdc++.h>

#define ri register signed

#define p(i) ++i

using namespace std;

namespace IO{

    char buf[1<<21],*p1=buf,*p2=buf;

    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++

    template<typename T>inline void read(T &x) {

        ri f=1;x=0;char ch=gc();

        while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}

        while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}

        x*=f;

    }

}

using IO::read;

namespace nanfeng{

    #define cmax(x,y) ((x)>(y)?(x):(y))

    #define cmin(x,y) ((x)>(y)?(y):(x))

    #define FI FILE *IN

    #define FO FILE *OUT

    typedef long long ll;

    static const int N=405,K=1e6+7;

    int cnt[K],b[N],sum[N][N],n,m,k;

    ll ans;

    inline int main() {

        // FI=freopen("nanfeng.in","r",stdin);

        // FO=freopen("nanfeng.out","w",stdout);

        read(n),read(m),read(k);

        for (ri i(1);i<=n;p(i)) {

            for (ri j(1),w;j<=m;p(j))

                read(w),sum[i][j]=(sum[i-1][j]+sum[i][j-1]+w+k-sum[i-1][j-1])%k;

        }

        for (ri i(0);i<n;p(i)) {

            for (ri j(i+1);j<=n;p(j)) {

                cnt[0]=1;

                for (ri l(1);l<=m;p(l)) ans+=cnt[b[l]=(sum[j][l]+k-sum[i][l])%k]++;

                for (ri l(1);l<=m;p(l)) cnt[b[l]]=0;

            }

        }

        printf("%lld\n",ans);

        return 0;

    }

}

int main() {return nanfeng::main();}

巴特西

题解 P3941 入阵曲

题解

最新文章

热门文章