( ext{E - Packing Under Range Regulations})
解法
将左端点从小到大排序，把对应的右端点插入优先队列。然后枚举盒子 (i) 放入当前优先队列第一个元素，删除后判断优先队列里第一个元素能否放入 (i+1) 之后的盒子。最后插入新的左端点对应右端点。
这样保证可以放置的情况下，右端点顺序是递增的。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-'),write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
#include <map>
#include <queue>
#include <vector>
using namespace std;
const int maxn=2e5+5;
priority_queue < int,vector<int>,greater<int> > q;
int n,idx;
map <int,int> mp;
vector <int> g[maxn];
int main() {
int x,y;
for(int T=read(9);T;--T) {
n=read(9); mp.clear();
while(!q.empty()) q.pop();
idx=0;
for(int i=1;i<=n;++i) {
x=read(9),y=read(9);
if(!mp.count(x)) {
mp[x]=++idx;
g[idx].clear();
}
g[mp[x]].push_back(y);
}
mp[1e9+1]=1;
int i=mp.begin()->first;
bool ans=0;
while(i<=1e9) {
x=mp[i];
for(int j=0;j<g[x].size();++j)
q.push(g[x][j]);
q.pop();
if(q.empty())
i=mp.lower_bound(i+1)->first;
else {
if(q.top()<=i) {
ans=1; break;
}
++i;
}
}
if(!q.empty()) ans=1;
puts(ans?"No":"Yes");
}
return 0;
}
( ext{G - Three Permutations})
解法
前几天才做了夫妻围坐问题… 但是还是不会做。令人生草。关于夫妻围坐问题可以翻翻 "精尽人亡" 这场比赛，但是目前状态是咕咕咕。
首先可以自然地联想到容斥原理，还是令 (A_i) 为 "满足 (i) 位置上是 (p_i) 或 (q_i)" 的方案集合。如果将 ((p_i,q_i)) 连边最后生成一个环的话就是原问题，但实际上本题可能生成多个环。不过很好的一点是一个连通块也只能是环，因为每个点的入度与出度都是 (1)。
所以问题实际上可以分解为：对每个环求解 (sum_{1le i_1<i_2<...<i_kle n} |A_{i_1}cap A_{i_2}cap ...cap A_{i_k}|)，然后 (mathcal O(n^2)) 的 (mathtt{dp}) 把答案拼起来。
对于大小为 (cnt) 的环，我们发现第 (i) 条边与 (p_i) 的交界可以视作 (i) 位置上是 (p_i)，(q_i) 同理。而且假设与 (p_i) 相邻的另一条边是 (j)（显然 (p_i=q_j)），那么 "满足 (i) 位置上是 (p_i)" 时，"满足 (i) 位置上是 (q_i)" 和 "满足 (j) 位置上是 (q_j)" 都是不可能成立的。转化到环上就是选取了第 (i) 条边与 (p_i) 的交界时，第 (i) 条边与 (q_i) 的交界和第 (j) 条边与 (q_j) 的交界都是不能选的。这就转化成了原问题。
"交界" 有 (2cdot cnt) 个，假设选 (k) 个条件。套用公式可得方案数为 (inom{2cdot cnt-k-1}{k-1}cdot frac{2cdot cnt}{k}cdot (n-k)!)。如果懒得求 (k) 的逆元以及减去 (log) 的求逆元复杂度，可以转化成这个式子：(left ( inom{2cdot cnt-k}{k}+inom{2cdot cnt-k-1}{k-1} ight )cdot (n-k)!)。
自环需要特判一下。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-'),write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
const int mod=1e9+7,maxn=3005;
int n,a[maxn],b[maxn],to[maxn];
int fac[maxn<<1],ifac[maxn<<1];
int tmp[maxn],dp[maxn];
bool vis[maxn];
int inv(int x,int y=mod-2) {
int r=1;
while(y) {
if(y&1) r=1ll*r*x%mod;
x=1ll*x*x%mod; y>>=1;
}
return r;
}
void init() {
fac[0]=1;
for(int i=1;i<=(n<<1);++i)
fac[i]=1ll*fac[i-1]*i%mod;
ifac[n<<1]=inv(fac[n<<1]);
for(int i=(n<<1)-1;i>=0;--i)
ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
int C(int n,int m) {
if(n<m or n<0 or m<0)
return 0;
return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
signed main() {
n=read(9); init();
for(int i=1;i<=n;++i)
a[i]=read(9);
for(int i=1;i<=n;++i)
b[i]=read(9),
to[a[i]]=b[i];
dp[0]=1;
for(int i=1;i<=n;++i) {
if(vis[i]) continue;
int cnt=0;
for(int j=i;!vis[j];j=to[j]) {
++cnt;
vis[j]=1;
}
for(int j=0;j<=n;++j)
tmp[j]=0;
for(int j=0;j<=cnt;++j) {
int inc=(C(cnt*2-j,j)+C(cnt*2-j-1,j-1))%mod;
if(cnt==1 and j==1) inc=1;
for(int k=0;k<=n-j;++k)
tmp[j+k]=(tmp[j+k]+1ll*dp[k]*inc%mod)%mod;
}
for(int j=0;j<=n;++j)
dp[j]=tmp[j];
}
int ans=0;
for(int i=0;i<=n;++i) {
int t=1ll*fac[n-i]*dp[i]%mod;
if(i&1) ans=(ans-t+mod)%mod;
else ans=(ans+t)%mod;
}
print(ans,'
');
return 0;
}