【思维】Luogu P3941 入阵曲

题目大意

洛谷链接

给出一个矩阵和 \(K\) ，问有多少子矩阵中的元素和能整除 \(K\)。

数据范围

\(2\leq n,m\leq 400\)，\(0\leq K\leq 10^6\)。

思路

暴力枚举 \(O(n^6)\)，二维前缀和优化 \(O(n^4)\)。

根据数据范围我们需要想出至少 \(O(n^3)\) 的方法。而枚举左上角或右下角的方法显然是不可取的，所以我们想怎么优化枚举矩阵的方法。

我们可以通过枚举上界和下界，从而规定矩阵的高度，从而得到许多等高矩阵。从而可以把其抽象为一维，则答案变成求一个序列中区间和能整除 \(K\) 的区间数量。

如图：

设前缀和为 \(sum\)，则

\[\because\ (sum[r]-sum[l-1])\ \mathrm{mod}\ K=0
\]

\[\therefore\ sum[r]\equiv sum[l-1]\pmod K
\]

所以我们可以开桶记录相同的余数来统计答案（每次找到相同的都加一下），不过有个需要细的地方就是余数为 \(0\) 的时候，此时需要统计三个答案，因为两个前缀和本身也是符合条件的。

代码

\(O(n^3)\) 100分代码：

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=400+10;

const int maxm=1e6+10;

int n,m,K,ans;

int a[maxn][maxn],sum[maxn][maxn],cnt[maxm],b[maxm];

inline int read(){

    int x=0,fopt=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=-1;

    for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;

    return x*fopt;

}

signed main(){

    n=read();m=read();K=read();

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++){

            a[i][j]=read();

            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

        }

    for(int i=1;i<=n;i++)

        for(int j=i;j<=n;j++){

            cnt[0]=1;

            for(int k=1;k<=m;k++){

                b[k]=(sum[j][k]-sum[i-1][k]+K)%K;

                ans+=cnt[b[k]];

                cnt[b[k]]++;

            }

            for(int k=1;k<=m;k++)

                cnt[b[k]]=0;

        }

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

    return 0;

}

\(O(n^4)\) 60分代码：

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=400+10;

int n,m,K,ans;

int a[maxn][maxn],sum[maxn][maxn];

inline int read(){

    int x=0,fopt=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=-1;

    for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;

    return x*fopt;

}

signed main(){

    n=read();m=read();K=read();

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++){

            a[i][j]=read();

            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

        }

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

            for(int k=i;k<=n;k++)

                for(int q=j;q<=m;q++){

                    if((sum[k][q]-sum[i-1][q]-sum[k][j-1]+sum[i-1][j-1])%K==0)

                        ans++;

                }

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

    return 0;

}

巴特西

【思维】Luogu P3941 入阵曲

题目大意

数据范围

思路

代码

最新文章

热门文章