1 条题解
-
1
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <map> // STL #include <string> #include <vector> #include <queue> #include <stack> #define mpr make_pair #define debug() puts("okkkkkkkk") using namespace std; typedef long long LL; const int inf = 1 << 26; // dp[i][j][h][l] 表示在点 (i,j),差值为h,小A还是uim取液体的方案数(0-->小A 1-->uim) // dp[i][j][h][1]+=(dp[i-1][j][(h-a[i][j]+k)%k][0]) // uim取,差值就变小了 // dp[i][j][h][1]+=(dp[i][j-1][(h-a[i][j]+k)%k][0] // dp[i][j][h][0]+=(dp[i-1][j][(h+a[i][j])%k][1]) // dp[i][j][h][0]+=(dp[i][j-1][(h+a[i][j])%k][1]) // 初始化:dp[i][j][a[i][j]][0]=1; // 一开始小A可以从任意点开始 int dp[805][805][20][2]; int n,m,k; int a[805][805]; const int mod=(int)1e9+7; int main(){ // freopen("Luogu1373.in","r",stdin); scanf("%d%d%d",&n,&m,&k);++k; // k+1会变成0,k不变 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); dp[i][j][a[i][j]%k][0]=1; } int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int h=0;h<=k;h++){ dp[i][j][h][0]=(dp[i][j][h][0]+dp[i-1][j][(h-a[i][j]+k)%k][1])%mod; dp[i][j][h][0]=(dp[i][j][h][0]+dp[i][j-1][(h-a[i][j]+k)%k][1])%mod; dp[i][j][h][1]=(dp[i][j][h][1]+dp[i-1][j][(h+a[i][j])%k][0])%mod; dp[i][j][h][1]=(dp[i][j][h][1]+dp[i][j-1][(h+a[i][j])%k][0])%mod; } } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)ans=(ans+dp[i][j][0][1])%mod; printf("%d\n",ans); return 0; }
- 1
信息
- ID
- 373
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 5
- 标签
- 递交数
- 3
- 已通过
- 3
- 上传者