CF293B Distinct Paths题解

Iceturky · 2024-07-07 10:25:05 · 题解

Link

这里会给出多种解法。

首先可以发现 n,m\leq 1000 是骗人的，用鸽巢搞一下发现 n+m-1\leq k ，范围很小可以直接搜。

但是直接只存左上角经过了哪些颜色进行暴力搜索会T，如何剪枝？

首先是可行性剪枝。如果剩下的可以用的颜色比从当前点往右下角走的步数还要少就直接寄了。

其次还有对称性。如果用一个这张棋盘上尚未出现的颜色，那么当前点是用这个颜色还是其他尚未出现过的颜色都是等价的。

根据这个有一个简单的基于dfs的实现。

code

const int N=12;

int apr[N][N]; 
int mp[N][N];
bool has[N];

int n,m,k;
int ans;

void dfs(int x,int y){
    if(y>m)
        x++,y=1;
    if(x>n){
        ans++;
        return;
    }
    apr[x][y]=apr[x][y-1]|apr[x-1][y];//左上角颜色并
    if(k-__builtin_popcount(apr[x][y])<n-x+m-y+1)//可行性
        return;
    if(mp[x][y]){//已经填过了
        if(apr[x][y]&(1<<(mp[x][y]-1)))
            return;
        apr[x][y]|=1<<(mp[x][y]-1);
        dfs(x,y+1);
    }else{
        int sum=0;
        bool tag=0;
        for(int i=((1<<k)-1)^apr[x][y];i;i^=lowbit(i)){
            if(has[__lg(lowbit(i))+1]){//已经出现过
                apr[x][y]|=lowbit(i);
                dfs(x,y+1);
                apr[x][y]^=lowbit(i);
            }else{//尚未出现过
                has[__lg(lowbit(i))+1]=1;
                if(tag==0){//还没计算过贡献
                    sum=ans;//留存快照
                    apr[x][y]|=lowbit(i);
                    dfs(x,y+1);
                    apr[x][y]^=lowbit(i);
                    sum=ans-sum;//与之前快照做差
                    tag=1;
                }else
                    ans+=sum;//所有没有用过的颜色在这里的贡献一样。
                has[__lg(lowbit(i))+1]=0;
            }
        }
    }
}

signed main(){
    n=read(),m=read(),k=read();
    if(n+m-1>k){
        print(0),pc('\n');
        return 0;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            has[mp[i][j]=read()]=1;//已经出现过的颜色
        }
    }
    dfs(1,1);
    print(ans%((int)1e9+7)),pc('\n');
    return 0;
}

还有一个tourist的程序实现。

他建立了若干映射，用当前枚举所填的颜色去映射到棋盘上已经实际填的颜色上去（当然可能实际什么都没填）。

最后判一下是否产生冲突即可。同时每一个没有实际对应颜色的填上的颜色都是可以随便填的。

放个代码

code by tourist

#include<bits/stdc++.h>
using namespace std;
const int md=1000000007;
int n,m,k;
int ans=0;
int a[42][42];
int bad[42][42][42];
int res[42][42];
int mp[42];
void go(int row,int col,int mc)
{
    if(row==n)
    {
        for(int c=1;c<=mc;c++)
            for(int qc=c+1;qc<=mc;qc++)
                if(mp[c]!=0&&mp[qc]!=0&&mp[c]==mp[qc])//看看有没有冲突
                    return;
        int free=0,cols=k;//free是自由元，没有实际映射颜色，可以随便填，cols则是还没有被实际填上的颜色（即被映射的颜色）
        for(int c=1;c<=mc;c++)
        {
            if(mp[c]==0)
                free++;//c这个颜色没有实际对应颜色
            else
                cols--;//有实际对应颜色，可用颜色减一
        }
        int cur=1;
        for(int c=1;c<=free;c++)
        {
            cur*=cols;//自由元贡献
            cols--;
        }
        ans+=cur;
        if(ans>=md)
            ans-=md;
        return;
    }
    for(int c=1;c<=k&&c<=mc+1;c++)
    {
        if(bad[row][col][c])
            continue;//左上角出现过这种颜色
        for(int x=row;x<n;x++)
            for(int y=col;y<m;y++)
                bad[x][y][c]++;//给右下角打标记
        res[row][col]=c;
        int ok=1;
        if(a[row][col]!=0)//有实际颜色
            if(mp[c]!=0&&mp[c]!=a[row][col])//产生冲突
                ok=0;
        if(ok)
        {
            bool flag=false;
            if(mp[c]==0)//还没有实际对应颜色
            {
                mp[c]=a[row][col];//放上这一个位置实际填的颜色，当然也可能没填
                flag=true;
            }
            int nmc=c>mc?c:mc;
            if(col<m-1)
                go(row,col+1,nmc);
            else
                go(row+1,0,nmc);
            if(flag)
                mp[c]=0;
        }
        for(int x=row;x<n;x++)
            for(int y=col;y<m;y++)
                bad[x][y][c]--;
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    if(n+m-1>k)
    {
        printf("%d\n",0);
        return 0;
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&a[i][j]);
    go(0,0,0);
    printf("%d\n",ans);
    return 0;
}

还有一份代码，实现的比较美观。

它通过传参来记录当前方案可以通过交换颜色来达到多少种方案。

code by SergeyRogulenko

int t[10][10];
int d[10][10];
int a[10][10];
int64 res;
int n, m, k;
int s[1024];

void go(int x, int y, int cmask, int64 w, int rem) {//分别表示到了哪里，用了哪些颜色，贡献与还有多少颜色没用过
    if (x == n) {
        res += w;//加上当前方案的贡献
        return;
    }   
    int mask = 0;//左上角的颜色
    if (x > 0)
        mask |= t[x-1][y];
    if (y > 0)
        mask |= t[x][y-1];
    if (mask & d[x][y]) return;//与右下角产生冲突
    if (a[x][y] >= 0) {
            t[x][y] = mask | (1 << a[x][y]);
        go(x + (y + 1) / m, (y + 1) % m, cmask, w, rem);
        return;
    }
    forn(i, k)
        if (!((mask|d[x][y]) & (1 << i)) && (cmask & (1 << i))) {//枚举用过的颜色
            t[x][y] = mask | (1 << i);
            go(x + (y + 1) / m, (y + 1) % m, cmask, w, rem);//直接搜
        }
    forn(i, k)
        if (!((mask|d[x][y]) & (1 << i)) && !(cmask & (1 << i))) {//枚举没用过的颜色
            t[x][y] = mask | (1 << i);
            go(x + (y + 1) / m, (y + 1) % m, cmask | (1 << i), w * rem, rem-1);//贡献数量增加，这个位置无论天rem里的哪一个颜色都是可以的，所以乘上rem
            break;//搜一遍即可
        }
} 

int64 calc(int cmask) {
    res = 0;
    int rem = k;
    forn(i, k)
        if (cmask & (1 << i))
            rem--;
    go(0, 0, cmask, 1, rem);
    return res;
}

int main ()
{
    cin >> n >> m >> k;
    if (n + m - 1 > k) {
        cout << 0 << endl;
        return 0;
    }
    forn(i, n)
        forn(j, m) {
            cin >> a[i][j];
            a[i][j]--;
        }
    int cmask = 0;
    ford(i, n)
        ford(j, m) {
            int mask = 0;
            if (a[i][j] != -1) {
                mask |= 1 << a[i][j];
            }
            cmask |= mask;
            if (i + 1 < n) {
                d[i][j] |= d[i+1][j];   
            }
            if (j + 1 < m) {
                d[i][j] |= d[i][j+1];   
            }//右下角
            if (d[i][j] & mask) {
                cout << 0 << endl;
                return 0;
            }
            d[i][j] |= mask;
        }
    cout << calc(cmask) % 1000000007 << endl;
    return 0;
}

上面的代码都是基于dfs，这题也能dp。

若从上到下，从左到右枚举的话，对于每一种颜色，我们只关心它最靠左的被填的位置的列下标。因为所有被填的数（不包括棋盘上已经有的）都在当前位置的上方（非严格），那么越靠左管辖区域就越大。

那么设 f_{x,y,S} 表示到了 (x,y) ，每一种颜色最靠左的下标为 S 的方案数。

发现每一种颜色的下标都是 [1,m+1] ，m+1 表示从未使用过。这个范围很小，可以用四位二进制数存，这样 S 的大小就是 2^{4\times10} 左右。显然装不满。

可以用map或umap来存，转移的时候直接遍历上一个位置的所有 S 。

我没写dp的版本，贴一个别人的代码。

code by tomasz.kociumaka

int a[50][50];
unordered_map<LL, int> M[100];

int us[10];

int main(){
    ios_base::sync_with_stdio(false);
    int n,m,k;
    cin >> n >> m >> k;
    if (n+m-1 > k) {
        cout << 0 << endl;
        return 0;
    }    
    REP(i, n) REP(j, m) {
        cin >> a[i][j];
        if (a[i][j] > 0) us[a[i][j]-1] = 1;
    }
    if (n < m) {
        REP(i, m) REP(j, i) swap(a[i][j], a[j][i]);
        swap(n,m);
    }
    if (n == 1 && m == 1) {
        if (a[0][0] == 0) {
            cout << k << endl;

        } else {
            cout << 1 << endl;
        }
        return 0;
    }
    int A = a[0][0];
    int B = a[n-1][m-1];
    if (A != 0) {
        REP(i, n) REP(j,m) {
            if (i == 0 && j == 0) continue;
            if (a[i][j] == A) {
                cout << "0" << endl;
                return 0;
            }
        } 
        us[A-1] = 0;
    }
    if (B != 0) {
        REP(i, n) REP(j, m) {
            if (i == n-1 && j == m-1) continue;
            if (a[i][j] == B) {
                cout << "0" << endl;
                return 0;
            }
        }
        us[B-1] = 0;
    }
    FOR(i, 1, k-1) {
        us[i] += us[i-1];
    }
    REP(i, n) REP(j, m) {
        if (a[i][j] != 0) a[i][j] = us[a[i][j]-1];
    }
    int mlt = 1;
    int rem = k-us[k-1];
    if (A == 0 && B == 0) mlt = rem*(rem-1);
    else if (A == 0 || B == 0) mlt = rem-1;
    //以上部分都是把第一个和最后一个位置给扣掉，因为这两个位置独占两种颜色，剪掉能减低复杂度
    LL z = 0;
    REP(i, k) {
        z = 16* z + 11;
    }
    M[1][z] = 1;
    int ph = 1;
    REP(i, n) REP(j, m) {
        if (i == 0 && j == 0) continue;
        if (i == n-1 && j == m-1) continue;
        REP(l,k-2) {//把两种颜色剪掉后就只有k-2种了
            if (a[i][j] > 0 && a[i][j] != l+1) continue;
            FORE(it, M[ph]) {
                LL v = it->X;
                LL c = (v>>(4*l))&15;
                if (((v>>(4*l))&15) <= j) continue;
                v ^= c<<(4*l);
                v |= j<<(4*l); 
                M[ph+1][v] += it->Y;
                M[ph+1][v] %= INF;
            }
        }
        ++ph; //下一个位置
    }
    LL res = 0;
    FORE(it, M[ph]) {
        res += it->Y;
        res %= INF;
    }
    cout << (res*mlt)%INF << endl;//乘上第一个和最后一个位置的贡献
    return 0;
}