人 傻 常 数 大
查看原帖
人 傻 常 数 大
245875
Ame__楼主2020/9/5 10:48

最后一个点T,求dalao帮忙卡个常QAQ

#include<bits/stdc++.h>
    
#define LL long long
    
#define _ 0
    
using namespace std;
    
/*Grievous Lady*/
    
template <typename _n_> void mian(_n_ & _x_){
    _x_ = 0;int _m_ = 1;char buf_ = getchar();
    while(buf_ < '0' || buf_ > '9'){if(buf_ == '-')_m_ =- 1;buf_ = getchar();}
    do{_x_ = _x_ * 10 + buf_ - '0';buf_ = getchar();}while(buf_ >= '0' && buf_ <= '9');_x_ *= _m_;
}
    
// #define int long long

#define mod 20110520

int r , c , endx , endy , mp[110][110] , tmp[110][110];

char chino;

unordered_map<int , LL> dp[2];

inline int oqs(int x , int y){
    return x << (y << 1);
}

#define add(x , val) \
{ \
    x %= mod; (x += val) %= mod; \
}

inline int DP(){
    int tmp = (1 << ((c + 1) << 1)) - 1;
    LL numnow = 0 , numnxt = 1 , ans = 0;
    dp[numnow][0] = 1;
    for(int i = 1;i <= r;i ++){
        for(int j = 1;j <= c;j ++){
            // cout << ans << '\n';
            dp[numnxt].clear();
            for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
                int S = k -> first , val = k -> second;
                int L = (S >> ((j - 1) << 1)) & 3 , R = (S >> (j << 1)) & 3;
                if(!mp[i][j]){
                    if(!L && !R) add(dp[numnxt][S] , val);
                    continue;
                }
                if(!L && !R){
                    if(mp[i][j + 1]) add(dp[numnxt][S ^ oqs(1 , j)] , val);
                    if(mp[i + 1][j]) add(dp[numnxt][S ^ oqs(1 , j - 1)] , val);
                    if(mp[i][j + 1] && mp[i + 1][j]) add(dp[numnxt][S ^ oqs(2 , j) ^ oqs(2 , j - 1)] , val);
                }
                if(L && !R){
                    if(L == 1 && R == 0){
                        if(mp[i][j + 1]) add(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(1 , j)] , val);
                        if(mp[i + 1][j] && L == 1) add(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(2 , j - 1)] , val);
                    }
                    if(L == 2 && R == 0){ 
                        add(dp[numnxt][S ^ oqs(L , j - 1)] , val);
                        if(mp[i][j + 1]) add(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(2 , j)] , val);
                    }
                }
                if(!L && R){
                    if(L == 0 && R == 1){
                        if(mp[i + 1][j]) add(dp[numnxt][S ^ oqs(R , j) ^ oqs(R , j - 1)] , val);
                        if(mp[i][j + 1] && R == 1) add(dp[numnxt][S ^ oqs(R , j) ^ oqs(2 , j)] , val);
                    }
                    if(L == 0 && R == 2){ 
                        add(dp[numnxt][S ^ oqs(R , j)] , val);
                        if(mp[i + 1][j]) add(dp[numnxt][S ^ oqs(R , j - 1) ^ oqs(R , j)] , val);
                    }
                }
                if(L == 1 && R == 1){
                    add(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j)] , val);
                }
                if(i == endx && j == endy){
                    if(L == 1 && R == 1) add(ans , val);
                    if(L == 0 && R == 2) add(ans , val);
                    if(L == 2 && R == 0) add(ans , val);
                    // return val;
                }
            }
            swap(numnow , numnxt);
        }
        dp[numnxt].clear();
        for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
            add(dp[numnxt][(k -> first << 2) & tmp] , k -> second);
        }
        swap(numnow , numnxt);
    }
    return ans;
}

inline int Ame_(){
    mian(r) , mian(c);
    for(int i = 1;i <= r;i ++)
		for(int j = 1;j <= c;j ++){
			cin >> chino;
			if(chino == '*') mp[i][j] = 0;
			else if(chino == '_') mp[i][j] = 1 , endx = i , endy = j;
		}
	if(r < c){
		for(int i = 1;i <= r;i ++)
			for(int j = 1;j <= c;j ++)
				tmp[j][i] = mp[i][j];
		swap(r , c);
		memset(mp , 0 , sizeof(mp));
		for(int i = 1;i <= r;i ++)
			for(int j = 1;j <= c;j ++)
				mp[i][j] = tmp[i][j];
		swap(endx , endy);
	}
    printf("%lld\n" , DP());
    return ~~(0^_^0);
}
    
int Ame__ = Ame_();
    
signed main(){;}

/*
3 3
___
_*_
___
*/
2020/9/5 10:48
加载中...