The 2024 Shanghai Collegiate Programming Contest G. 象棋大师（计数状元dp） · znzryb
## 思路讲解
因为方向是确定的，可以从前往后推导。
```cpp
for(int s=cnts-1;s>=0;--s){
for(int i=0;i<=N;++i){
for(int j=0;j<=N;++j){
if(danger[s][i][j]) continue; // danger,continue
bitset<15> bi(s);
// set<array<ll,2> > mas;
// for(int k=0;k<M;++k){if(bi[k]) mas.insert(ma[k]);}
for(int k=0;k<2;++k){
ll u=i+di[k],v=j+dj[k];
if(u<0 || u>N) continue;
if(v<0 || v>N) continue;
if(danger[s][u][v]) continue;
ll idx=-1;
for(int l=0;l<M;++l){
if(ma[l][0]==u && ma[l][1]==v && bi[l]){idx=l;break;}
}
if(idx!=-1){
if(danger[s-(1<<idx)][u][v]) continue;
dp[s-(1<<idx)][u][v]+=dp[s][i][j];
dp[s-(1<<idx)][u][v]%=mod;
}else{
dp[s][u][v]+=dp[s][i][j];
dp[s][u][v]%=mod;
}
}
}
}
}
```
## AC代码
327ms
[https://codeforces.com/gym/105229/my](https://codeforces.com/gym/105229/my)
::: 源代码
```cpp
#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":"<<x<<"\n";
using namespace std;
using ll = long long;
constexpr ll mod=998244353;
/*
*/
ll dp[1100][105][105];
bool danger[1100][105][105]; // 0=safe 1=danger 2=horse
ll dx[]={1,2,2,-1,-2,1,-1,-2};
ll dy[]={2,1,-1,2,1,-2,-2,-1};
ll bx[]={0,1,1, 0,-1,0,0,-1};
ll by[]={1,0,0, 1,0,-1,-1,0};
ll di[]={0,1};
ll dj[]={1,0};
inline void solve(){
ll N,M;
cin>>N>>M;
vector<array<ll,2> > ma;
for(int i=0;i<M;++i){
ll x,y;
cin>>x>>y;
ma.push_back({x,y});
// mas.insert({x,y});
}
// dpi j s
ll cnts=(1<<M); // 状态数量
for(int s=0;s<=cnts;++s){
bitset<15> bi(s);
vector<array<ll,2> > wp;
set<array<ll,2> > st;
for(int i=0;i<M;++i){
if(bi[i]){
wp.push_back(ma[i]);
st.insert(ma[i]);
// ll x=ma[i][0],y=ma[i][1];
// danger[s][x][y]=2;
}
}
for(int i=0;i<wp.size();++i){
ll x=wp[i][0],y=wp[i][1];
for(int j=0;j<8;++j){
ll u=x+dx[j],v=y+dy[j];
if(u<0 || u>N) continue;
if(v<0 || v>N) continue;
ll bbx=x+bx[j],bby=y+by[j];
// 别马脚了
if(st.find({bbx,bby})!=st.end()) continue;
danger[s][u][v]=true;
}
}
}
if(!danger[cnts-1][0][0]) dp[cnts-1][0][0]=1;
for(int s=cnts-1;s>=0;--s){
for(int i=0;i<=N;++i){
for(int j=0;j<=N;++j){
if(danger[s][i][j]) continue; // danger,continue
bitset<15> bi(s);
// set<array<ll,2> > mas;
// for(int k=0;k<M;++k){if(bi[k]) mas.insert(ma[k]);}
for(int k=0;k<2;++k){
ll u=i+di[k],v=j+dj[k];
if(u<0 || u>N) continue;
if(v<0 || v>N) continue;
if(danger[s][u][v]) continue;
ll idx=-1;
for(int l=0;l<M;++l){
if(ma[l][0]==u && ma[l][1]==v && bi[l]){idx=l;break;}
}
if(idx!=-1){
if(danger[s-(1<<idx)][u][v]) continue;
dp[s-(1<<idx)][u][v]+=dp[s][i][j];
dp[s-(1<<idx)][u][v]%=mod;
}else{
dp[s][u][v]+=dp[s][i][j];
dp[s][u][v]%=mod;
}
}
}
}
}
ll ans=0;
for(int s=cnts-1;s>=0;--s){
ans+=dp[s][N][N];
ans%=mod;
}
ans%=mod;
if(ans<0) ans+=mod;
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// ll lT;
// cin>>lT;
// while(lT--){
// solve();
// }
solve();
return 0;
}
/*
*/
```
:::
## 心路历程（WA，TLE，MLE……）
TLE，set常数太大。
::: 源代码
```cpp
#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":"<<x<<"\n";
using namespace std;
using ll = long long;
constexpr ll mod=998244353;
/*
*/
ll dp[1100][105][105];
bool danger[1100][105][105]; // 0=safe 1=danger 2=horse
ll dx[]={1,2,2,-1,-2,1,-1,-2};
ll dy[]={2,1,-1,2,1,-2,-2,-1};
ll bx[]={0,1,1, 0,-1,0,0,-1};
ll by[]={1,0,0, 1,0,-1,-1,0};
ll di[]={0,1};
ll dj[]={1,0};
inline void solve(){
ll N,M;
cin>>N>>M;
vector<array<ll,2> > ma;
for(int i=0;i<M;++i){
ll x,y;
cin>>x>>y;
ma.push_back({x,y});
// mas.insert({x,y});
}
// dpi j s
ll cnts=(1<<M); // 状态数量
for(int s=0;s<=cnts;++s){
bitset<15> bi(s);
vector<array<ll,2> > wp;
set<array<ll,2> > st;
for(int i=0;i<M;++i){
if(bi[i]){
wp.push_back(ma[i]);
st.insert(ma[i]);
// ll x=ma[i][0],y=ma[i][1];
// danger[s][x][y]=2;
}
}
for(int i=0;i<wp.size();++i){
ll x=wp[i][0],y=wp[i][1];
for(int j=0;j<8;++j){
ll u=x+dx[j],v=y+dy[j];
if(u<0 || u>N) continue;
if(v<0 || v>N) continue;
ll bbx=x+bx[j],bby=y+by[j];
// 别马脚了
if(st.find({bbx,bby})!=st.end()) continue;
danger[s][u][v]=true;
}
}
}
if(!danger[cnts-1][0][0]) dp[cnts-1][0][0]=1;
for(int s=cnts-1;s>=0;--s){
for(int i=0;i<=N;++i){
for(int j=0;j<=N;++j){
if(danger[s][i][j]) continue; // danger,continue
bitset<15> bi(s);
set<array<ll,2> > mas;
for(int k=0;k<M;++k){if(bi[k]) mas.insert(ma[k]);}
for(int k=0;k<2;++k){
ll u=i+di[k],v=j+dj[k];
if(u<0 || u>N) continue;
if(v<0 || v>N) continue;
if(danger[s][u][v]) continue;
if(mas.find({u,v})!=mas.end()){
ll idx=0;
for(int l=0;l<M;++l){
if(ma[l][0]==u && ma[l][1]==v){idx=l;break;}
}
if(danger[s-(1<<idx)][u][v]) continue;
dp[s-(1<<idx)][u][v]+=dp[s][i][j];
dp[s-(1<<idx)][u][v]%=mod;
}else{
dp[s][u][v]+=dp[s][i][j];
dp[s][u][v]%=mod;
}
}
}
}
}
ll ans=0;
for(int s=cnts-1;s>=0;--s){
ans+=dp[s][N][N];
ans%=mod;
}
if(ans<0) ans+=mod;
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// ll lT;
// cin>>lT;
// while(lT--){
// solve();
// }
solve();
return 0;
}
/*
*/
```
:::