涂抹果酱

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2339 字
N行M列蛋糕，3种果酱；相邻不能同色；第K行
一本通
练习
正文

/*
原题：T1594 「一本通 5.4 练习 1」涂抹果酱 (TYVJ)
题意：N 行 M 列(M≤5)蛋糕，3 种果酱(1/2/3)；相邻(上下左右)不能同色；第 K 行已固定，求方案数 mod 10^6。
思路：按列状压(M≤5)。先枚举所有合法单行方案（行内相邻列颜色不同），再要求相邻两行同列颜色不同。
     以第 K 行为强制状态做逐行 DP：dp[i][p] 为前 i 行以方案 p 结尾的方案数，p 与上一行逐列不同。
复杂度：时间 O(N·S²)，空间 O(S)，S≤3^M（M=5 时 S≤243，实际合法单行 ≤48）。
易错点：1) 取模为 10^6；
       2) 第 K 行给定方案本身必须合法，否则直接输出 0；
       3) 仅 4-邻接不同色，不含对角与“连续三个同色”。
*/
#include <bits/stdc++.h>
using namespace std;
const int MOD=1000000;
int main(){
    int N,M,K;
    if(!(cin>>N>>M>>K)) return 0;
    vector<int> fixedRow(M);
    for(int j=0;j<M;j++) cin>>fixedRow[j];
    // 枚举所有合法单行方案：相邻列颜色不同（颜色编码为 0/1/2）
    vector<int> pat;          // 每行方案的整数编码
    vector<vector<int>> col;  // 每方案各列颜色
    int total=1;
    for(int i=0;i<M;i++) total*=3;
    for(int code=0;code<total;code++){
        int c=code;
        bool okp=true;
        vector<int> tmp(M);
        for(int j=M-1;j>=0;j--){ tmp[j]=c%3; c/=3; }
        for(int j=0;j+1<M;j++) if(tmp[j]==tmp[j+1]){ okp=false; break; }
        if(okp){ pat.push_back(code); col.push_back(tmp); }
    }
    int S=pat.size();
    // 单行间兼容性：同列颜色必须不同
    vector<vector<bool>> compat(S,vector<bool>(S,false));
    for(int i=0;i<S;i++) for(int j=0;j<S;j++){
        bool okc=true;
        for(int c2=0;c2<M;c2++) if(col[i][c2]==col[j][c2]){ okc=false; break; }
        compat[i][j]=okc;
    }
    // 定位第 K 行给定方案的编码
    int givencode=0;
    for(int j=0;j<M;j++) givencode=givencode*3+(fixedRow[j]-1);
    int gidx=-1;
    for(int i=0;i<S;i++) if(pat[i]==givencode){ gidx=i; break; }
    if(gidx<0){ cout<<0<<"\n"; return 0; }
    // dp：用前一行的方案集合，并引入“空状态” S 表示第 0 行之前（与任意方案兼容）
    vector<long long> prev(S+1,0);
    prev[S]=1;
    for(int r=1;r<=N;r++){
        vector<long long> cur(S+1,0);
        if(r==K){
            long long sum=0;
            for(int q=0;q<=S;q++) if(prev[q]>0){
                if(q==S || compat[gidx][q]) sum=(sum+prev[q])%MOD;
            }
            cur[gidx]=sum;
        }else{
            for(int p=0;p<S;p++){
                long long sum=0;
                for(int q=0;q<=S;q++) if(prev[q]>0){
                    if(q==S || compat[p][q]) sum=(sum+prev[q])%MOD;
                }
                cur[p]=sum;
            }
        }
        prev=move(cur);
    }
    long long ans=0;
    for(int p=0;p<S;p++) ans=(ans+prev[p])%MOD;
    cout<<ans<<"\n";
    return 0;
}
涂抹果酱

正文

一本通·提高篇的其它内容
