洛谷 1373 小a和uim之大逃离

时间:2023-03-08 16:17:03
洛谷 1373 小a和uim之大逃离
/*
很容易想到f[i][j][k][l][01] 表示到ij点 两个人得分为kl 01表示这一步谁走的
因为起点不同 路径不同 所以要枚举起点..
时间复杂度 O(nmk*nmk)
空间复杂度 O(2*nmkk)
超时爆空间.....
40分
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 810
#define mod 1000000007
using namespace std;
int n,m,K,ans,a[maxn][maxn];
int f[][][][][];
void Clear(int x,int y)
{
for(int i=x;i<=n;i++)
for(int j=y;j<=m;j++)
for(int k=;k<=K;k++)
for(int l=;l<=K;l++)
{
f[i][j][k][l][]=;
f[i][j][k][l][]=;
}
}
int main()
{
scanf("%d%d%d",&n,&m,&K);K++;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&a[i][j]);
for(int x=;x<=n;x++)
for(int y=;y<=m;y++)
{
Clear(x,y);
f[x][y][a[x][y]%K][][]=;
for(int i=x;i<=n;i++)
for(int j=y;j<=m;j++)
for(int k=;k<K;k++)
for(int l=;l<K;l++)
{
if(i+<=n)
{
f[i+][j][(k+a[i+][j])%K][l][]=(f[i+][j][(k+a[i+][j])%K][l][]+f[i][j][k][l][])%mod;
f[i+][j][k][(l+a[i+][j])%K][]=(f[i+][j][k][(l+a[i+][j])%K][]+f[i][j][k][l][])%mod;
}
if(j+<=m)
{
f[i][j+][(k+a[i][j+])%K][l][]=(f[i][j+][(k+a[i][j+])%K][l][]+f[i][j][k][l][])%mod;
f[i][j+][k][(l+a[i][j+])%K][]=(f[i][j+][k][(l+a[i][j+])%K][]+f[i][j][k][l][])%mod;
}
if(k==l)ans=(ans+f[i][j][k][l][])%mod;
}
}
printf("%d\n",ans);
return ;
}
/*
其实刚才的状态可以降一维 把kl改为两个人的差值
但是会出现负数 考试的时候想到数组平移 但是答案就不对了....
然后打了暴力 6层循环 美美的~ 后来终于在眼泪中明白 数组平移个卵...
因为在Mod的意义下 平移之后状态就不对应了
不平移mod完之后在+K不就好了嘛
还有就是傻傻的枚举起点了..赋好初值 从1 1开始就好了吗
反正最后统计方案数 互相之间不影响
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 810
#define mod 1000000007
using namespace std;
int n,m,K,ans,a[maxn][maxn];
int f[maxn][maxn][][];
int main()
{
scanf("%d%d%d",&n,&m,&K);K++;
memset(f,,sizeof(f));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
f[i][j][a[i][j]%K][]=;
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
for(int k=;k<K;k++)
{
if(i+<=n)
{
f[i+][j][(k+a[i+][j])%K][]=(f[i+][j][(k+a[i+][j])%K][]+f[i][j][k][])%mod;
f[i+][j][(k-a[i+][j]+K)%K][]=(f[i+][j][(k-a[i+][j]+K)%K][]+f[i][j][k][])%mod;
}
if(j+<=m)
{
f[i][j+][(k+a[i][j+])%K][]=(f[i][j+][(k+a[i][j+])%K][]+f[i][j][k][])%mod;
f[i][j+][(k-a[i][j+]+K)%K][]=(f[i][j+][(k-a[i][j+]+K)%K][]+f[i][j][k][])%mod;
}
if(k==)ans=(ans+f[i][j][k][])%mod;
}
printf("%d\n",ans);
return ;
}