https://www.luogu.org/problem/show?pid=1373

題目背景

小a和uim來(lái)到雨林中探險(xiǎn)。突然一陣北風(fēng)吹來(lái)，一片烏云從北部天邊急涌過(guò)來(lái)，還伴著一道道閃電，一陣陣?yán)茁暋x那間，狂風(fēng)大作，烏云布滿了天空，緊接著豆大的雨點(diǎn)從天空中打落下來(lái)，只見(jiàn)前方出現(xiàn)了一個(gè)披頭散發(fā)、青面獠牙的怪物，低沉著聲音說(shuō)：“呵呵，既然你們來(lái)到這，只能活下來(lái)一個(gè)！”。小a和他的小伙伴都驚呆了！

題目描述

瞬間，地面上出現(xiàn)了一個(gè)n*m的巨幅矩陣，矩陣的每個(gè)格子上有一坨0~k不等量的魔液。怪物各給了小a和uim一個(gè)魔瓶，說(shuō)道，你們可以從矩陣的任一個(gè)格子開(kāi)始，每次向右或向下走一步，從任一個(gè)格子結(jié)束。開(kāi)始時(shí)小a用魔瓶吸收地面上的魔液，下一步由uim吸收，如此交替下去，并且要求最后一步必須由uim吸收。魔瓶只有k的容量，也就是說(shuō)，如果裝了k+1那么魔瓶會(huì)被清空成零，如果裝了k+2就只剩下1，依次類(lèi)推。怪物還說(shuō)道，最后誰(shuí)的魔瓶裝的魔液多，誰(shuí)就能活下來(lái)。小a和uim感情深厚，情同手足，怎能忍心讓小伙伴離自己而去呢？沉默片刻，小a靈機(jī)一動(dòng)，如果他倆的魔瓶中魔液一樣多，不就都能活下來(lái)了嗎？小a和他的小伙伴都笑呆了！

現(xiàn)在他想知道他們都能活下來(lái)有多少種方法。

輸入輸出格式

輸入格式：

?

第一行，三個(gè)空格隔開(kāi)的整數(shù)n，m，k

接下來(lái)n行，m列，表示矩陣每一個(gè)的魔液量。同一行的數(shù)字用空格隔開(kāi)。

?

輸出格式：

?

一個(gè)整數(shù)，表示方法數(shù)。由于可能很大，輸出對(duì)1 000 000 007取余后的結(jié)果。

?

輸入輸出樣例

輸入樣例#1：
2 2 3 1 1 1 1 輸出樣例#1：
4

說(shuō)明

【題目來(lái)源】

lzn改編

【樣例解釋】

樣例解釋：四種方案是：(1,1)->(1,2),(1,1)->(2,1),(1,2)->(2,2),(2,1)->(2,2)。

【數(shù)據(jù)范圍】

對(duì)于20%的數(shù)據(jù)，n,m<=10,k<=2

對(duì)于50%的數(shù)據(jù)，n,m<=100,k<=5

對(duì)于100%的數(shù)據(jù)，n,m<=800,1<=k<=15

?

dp[i][j][h][0/1] 表示 走到了第i行第j列，此時(shí)（小a的魔液-uim的魔液）%（k+1）=h，這一步是小a/uim吸收的方案數(shù)

因?yàn)轭}目中說(shuō)裝了k+1時(shí)會(huì)變?yōu)?，所以模數(shù)為k+1

為什么差值可以取模？

還是因?yàn)?裝到>k時(shí)，數(shù)量會(huì)清0

第一個(gè)人比第二個(gè)人多h還是少h 對(duì)轉(zhuǎn)移沒(méi)有影響

?

#include<cstdio> using namespace std; int a[801][801],dp[801][801][16][2]; #define mod 1000000007 void ADD(int &x,int y) {x+=y; x-=(x>=mod) ? mod : 0; } int main() {int n,m,k;scanf("%d%d%d",&n,&m,&k);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;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int h=0;h<k;h++){ADD(dp[i][j][h][0],(dp[i-1][j][(h-a[i][j]+k)%k][1]+dp[i][j-1][(h-a[i][j]+k)%k][1])%mod);ADD(dp[i][j][h][1],(dp[i-1][j][(h+a[i][j])%k][0]+dp[i][j-1][(h+a[i][j])%k][0])%mod);}int ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ans=(ans+dp[i][j][0][1])%mod;printf("%d",ans); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/TheRoadToTheGold/p/7666127.html

總結(jié)

以上是生活随笔為你收集整理的洛谷1373 小a和uim之大逃离的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。