8.25考试总结

find

由于某些不可告知的原因,暂时不公开

page

原题,搞一个堆来贪心的选,每次选择一个下一个离得最远的点扔出去

这样正确性显然

如果一个数在堆里,我们要把他的nxt修改一下

这个貌似用堆不太好维护

我们就考虑换成set,因为这个数一定是最小的

直接搞搞就可以了

//STL重度依赖症QAQ 
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<set>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 3e5 + 3;
int a[N],nxt[N];
int n,k;
int pos[N];
bool book[N];
int ans;

multiset < pii > s;
multiset < pii >::iterator it;
inline int read(){
    int v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;
}
int main(){
    freopen("page.in","r",stdin);
    freopen("page.out","w",stdout);
    n = read(),k = read();
    for(int i = 1;i <= n;++i) {
        a[i] = read();
        if(pos[a[i]]) nxt[pos[a[i]]] = i;
        pos[a[i]] = i;
    }
    for(int i = 1;i <= n;++i) if(!nxt[i]) nxt[i] = n + 1;
    for(int i = 1;i <= n;++i){
        if(book[a[i]]){
            it = s.begin();
            pii x = *it;
            s.erase(it);
            s.insert(mk(nxt[i],i));
            continue;
        }
        if(s.size() < k){
            ans++;
            book[a[i]] = 1;
            s.insert(mk(nxt[i],i));
            continue;
        }
        ans++;
        it = s.end();it--;
        pii x = *it;
        s.erase(it);
        s.insert(mk(nxt[i],i));
        book[a[x.se]] = 0;
        book[a[i]] = 1;
    }
    printf("%d\n",ans);
    return 0;
}

graph

首先,模型转化,题目变成了

给你\(n\)个连通块,连通块内的点不能在连通块内的位置

求合法的排列个数

首先\(m = 0\)怎么做

所有的连通块的大小都是\(1\)的本质是错排

我们回想一下错排的容斥写法
\[ ans = \sum_{i = 0}^n(-1)^i\left(\begin{array}{l}{i} \\ {n}\end{array}\right)(n - i)! \]
强制\(i\)个点在不合法的位置上,其余的点随便排

接下来我们进行推广,当连通块大小不为\(0\)是,我们就不能这么算了

但我们还是考虑如何算出至少有\(j\)个点不合法的方案数

之后发现这个东西之和连通块的大小有关

我们设\(g_{i,j}\)表示大小为\(i\)的连通块,选了\(j\)个点的方案数,很明显,这\(j\)个点都是不合法的
\[ g_{i,j} = \left(\begin{array}{l}{i} \\ {j}\end{array}\right)\times\frac{i!}{(i - j)!} \]
前面就是我们选出\(j\)个点,后面是乘法原理

第一个点有\(i\)种选择,第二个点有\(i - 1\)个

所以就是\(i \times(i - 1)\times\dots\times(i - j + 1) = \frac{i!}{(i - j)!}\)

那么我们设\(f_{i,j}\)表示考虑了前\(i\)个连通块至少有\(j\)个点不合法的方案数

转移就是枚举这个连通块选了多少了不合法点
\[ f_{i,j }= \sum_{k = 0}^{size_i}f_{i - 1,j - k}\times{g_{size_i,k}} \]
这样我们在像错排那样把答案容斥出来就好了

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 2003;
const LL mod = 1e9 + 7;
LL f[N][N];
LL g[N][N];
int n,m,tot;
int fa[N];
int size[N];
int be[N];
LL inv[N],fac[N];
inline int getf(int x){ 
    return fa[x] == x ? x : fa[x] = getf(fa[x]);
}
inline int read(){
    int v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;
}
inline LL quick(LL x,LL y){
    LL res = 1;
    while(y){
        if(y & 1) res = res * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return res;
} 
inline LL C(LL x,LL y){
    if(x < y) return 0;
    return fac[x] * inv[y] % mod * inv[x - y] % mod;
}
inline LL up(LL x){
    if(x >= mod) x -= mod;
    return x;
}
int main(){
    n = read(),m = read();
    fac[0] = inv[0] = 1;
    for(int i = 1;i <= n;++i){
        fac[i] = fac[i - 1] * i % mod; 
        inv[i] = quick(fac[i],mod - 2); 
    }
    for(int i = 1;i <= n;++i) fa[i] = i;
    for(int i = 1;i <= m;++i){
        int u = getf(read()),v = getf(read());  
        fa[u] = v;
    }
    for(int i = 1;i <= n;++i){
        int x = getf(i);
        be[i] = x;
    //  if(x == i) tot++;
        size[x]++;
    }
    for(int i = 1;i <= n;++i){
        if(size[i]) size[++tot] = size[i];  
    }
    for(int i = 0;i <= n;++i)
        for(int j = 0;j <= i;++j)
            g[i][j] = C(i,j) * fac[i] % mod * inv[i - j] % mod;
    f[0][0] = 1;
    //printf("%d ",tot);
    //for(int i = 1;i <= tot;++i) printf("%d ",size[i]);puts("");
    for(int i = 1;i <= tot;++i){
        for(int j = 0;j <= n;++j){
            for(int k = 0;k <= min(j,size[i]);++k){
                f[i][j] = up(f[i][j] + f[i - 1][j - k] * g[size[i]][k] % mod);
            }
        }   
    }
    LL ans = 0;
    for(int i = 0;i <= n;++i){
        if(i & 1) ans -= f[tot][i] * fac[n - i] % mod;
        else ans += f[tot][i] * fac[n - i] % mod;   
    }
    printf("%lld\n",(ans % mod + mod) % mod);
    return 0;
}