【题解】P1373 小a和uim之大逃离

时间：2023-03-09 01:12:29
【题解】P1373 小a和uim之大逃离

【题解】P1373 小a和uim之大逃离

考虑到可能会MLE，考虑状态压缩一下

由于只要得到他们的差就行了，所以直接少记录一维就好了

\(dp(i,j,r,1/0)\)表示在\(i,j\)点，当前uim-a=\(r\)，这个节点是\(a/uim\)选择装瓶子的方案数，转移显然

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(c<48||c>57)f|=c==45,c=getchar();

      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxn=805;

const int mod=1e9+7;

int dp[maxn][maxn][21][2];

int map[maxn][maxn];

int n,m,K,ans;

int main(){

      //freopen("in.in","r",stdin);

      n=qr();m=qr();K=qr()+1;

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

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

		  map[t][i]=qr()%K;

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

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

		  dp[t][i][map[t][i]][0]=1;

      for(int t=1;t<=n;++t){

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

		  for(int k=0;k<K;++k){

			int fr=(k-map[t][i]+K)%K;

			dp[t][i][k][0]=(dp[t][i][k][0]+dp[t-1][i][fr][1]+dp[t][i-1][fr][1])%mod;

			fr=(k+map[t][i])%K;

			dp[t][i][k][1]=(dp[t][i][k][1]+dp[t-1][i][fr][0]+dp[t][i-1][fr][0])%mod;

		  }

		  ans=(ans+dp[t][i][0][1])%mod;

	    }

      }

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

      return 0;

}

相关文章