题解：P12917 [POI 2021/2022 R3] 小矮人派对 2 / Impreza krasnali 2
hb314
·
·
题解
因为每个数如果有某个人提到了他，则他存在的区间长度一定 \le3，没有提到过的数就是哪里都可以放，所以用 0 占位，最后乘上排列就可以了。
那么我们就有一个 \mathcal O(n^2) 的算法。
外面的优化不了，就只能优化枚举多少个 $0$。因为我们不重复地填完了已知的所有数字，所以剩下未知数字填 $0$ 的位置一定就能填完。
代码有个细节就是要处理每个数的区间的交，而不是并。因为并的话长度区间超过 $3$（其中有无效的位置），就无法通过记录前两个数字来判断合法。
```cpp
#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,long long>dp[2];
const long long mod=1000000007;
vector<int>v[100010];
int a[100010],bj1[100010],bj2[100010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];bj2[a[i]]=i;
if(bj1[a[i]]!=0){
if(i-bj1[a[i]]>=3){
cout<<"0\n";
return 0;
}
}else{
bj1[a[i]]=i;
}
}
int wjy=0;
for(int i=1;i<=n;i++){
if(bj1[i]==0)wjy++;
else if(bj2[i]-bj1[i]==0){
int x=bj2[i];
v[x].emplace_back(i);
v[x+1].emplace_back(i);
v[x-1].emplace_back(i);
}else if(bj2[i]-bj1[i]==1){
int x=bj2[i];
v[x].emplace_back(i);
v[x-1].emplace_back(i);
}else if(bj2[i]-bj1[i]==2){
int x=bj2[i];
v[x-1].emplace_back(i);
}
}
for(int i=0;i<=n;i++){
v[i].emplace_back(0LL);
}
for(int i:v[1]){
dp[1][make_pair(i,0)]=1;
}
for(int i=2;i<=n;i++){
dp[i&1].clear();
for(int p:v[i-1]){
for(int q:v[i-2]){
if(!dp[((i&1)^1)].count(make_pair(p,q)))continue;
for(int k:v[i]){
if(k!=0&&(k==p||k==q))continue;
if(p!=0&&(k==p||p==q))continue;
if(i!=2&&q!=0&&(k==q||p==q))continue;
if(a[i-1]==p||a[i-1]==k||a[i-1]==q){
dp[i&1][make_pair(k,p)]+=dp[((i&1)^1)][make_pair(p,q)];
dp[i&1][make_pair(k,p)]%=mod;
}
}
}
}
}
long long ans=0;
for(int p:v[n]){
for(int q:v[n-1]){
if(a[n]==p||a[n]==q){
ans=(ans+dp[n&1][make_pair(p,q)])%mod;
}
}
}
for(int i=1;i<=wjy;i++){
ans=ans*i%mod;
}
cout<<ans;
return 0;
}
```