HDU 4832 百度之星初賽：網格走位 DP + 組合數計算

問題重述

n×m 網格，起點 (x0,y0)。每步可移動 ±1 或 ±2（不可不動），共 k 步。求落在任意格子的方案數模 9999991。n,m≤1000, k≤1000。

核心觀察：橫縱向獨立 + 組合數分配步數

水平移動與垂直移動相互獨立。設水平用 i 步，垂直用 k-i 步。
方案數 = Σ_{i=0..k} C(k,i) * waysX(i) * waysY(k-i)。

單維 DP：dp[step][pos] = 走 step 步到達 pos 的方案數

for(step=1..k)
  for(pos=1..len)
    for(delta=-2..2, delta!=0)
      if(1≤pos+delta≤len)
        dp[pos+delta][step] += dp[pos][step-1];

初始 dp[start][0]=1。
每步轉移 O(len·k·4)，len≤1000, k≤1000 共 4e6，極快。

組合數預計算

C[n][k] = C[n-1][k-1] + C[n-1][k] (mod MOD)，n≤1000。

完整 C++ 代碼

#include 
using namespace std;
const int MOD = 9999991;
const int MAXN = 1010;

int C[MAXN][MAXN];
int dpX[MAXN][MAXN], dpY[MAXN][MAXN];
int sumX[MAXN], sumY[MAXN];

void initComb() {
    for(int i=0;i> T;
    for(int tc=1; tc<=T; ++tc) {
        int n,m,k,x0,y0; cin >> n >> m >> k >> x0 >> y0;
        memset(dpX,0,sizeof(dpX)); memset(dpY,0,sizeof(dpY));
        dpX[y0][0]=1; dpY[x0][0]=1; // 注意：題目 x 對應行(垂直), y 對應列(水平)

        for(int step=1; step<=k; ++step) {
            for(int pos=1; pos<=n; ++pos) // 垂直方向 n 行
                for(int d=-2; d<=2; ++d) if(d!=0) {
                    int np=pos+d;
                    if(np>=1 && np<=n) dpX[np][step] = (dpX[np][step] + dpX[pos][step-1]) % MOD;
                }
            for(int pos=1; pos<=m; ++pos) // 水平方向 m 列
                for(int d=-2; d<=2; ++d) if(d!=0) {
                    int np=pos+d;
                    if(np>=1 && np<=m) dpY[np][step] = (dpY[np][step] + dpY[pos][step-1]) % MOD;
                }
        }

        for(int i=0;i<=k;++i) {
            sumX[i]=sumY[i]=0;
            for(int pos=1;pos<=n;++pos) sumX[i] = (sumX[i] + dpX[pos][i]) % MOD;
            for(int pos=1;pos<=m;++pos) sumY[i] = (sumY[i] + dpY[pos][i]) % MOD;
        }

        long long ans=0;
        for(int i=0;i<=k;++i) {
            ans = (ans + 1LL * C[k][i] * sumX[i] % MOD * sumY[k-i]) % MOD;
        }
        cout << "Case #" << tc << ":\n" << ans << '\n';
    }
    return 0;
}

關鍵細節

• 題目坐標 (x0,y0)：x 為行號（垂直），y 為列號（水平），代碼中 dpX 對應垂直，dpY 對應水平。
• 移動步長 ±1, ±2，不可 0。
• 模數 9999991 非質數，但僅用加法/乘法，無需逆元。
• 答案公式：Σ C(k,i) * sumX[i] * sumY[k-i]，sumX[i] 為垂直用 i 步的總方案數。

複雜度

• 預計算組合數 O(MAXN²)。
• 每測試用例 O(k·(n+m)) ≈ 2e6。