题目太水了,是手速场。

A

如果 $a,b,c,d,e,f > 0$,那么就是判断转换效率是否 $>1$,也就是 $\frac{bdf}{ace}>1 \Rightarrow bdf > ace$。

但是会有 $0$ 的情况,我们发现我们需要特判 $c=0,d \neq 0$ 和 $a=0,b,d \neq 0$ 的情况,剩下的情况都能用上式判断。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

int main(){
    // freopen("A.in","r",stdin);
    // freopen("A.out","w",stdout);
    int T;scanf("%d",&T);
    while(T--){
        LL a,b,c,d,e,f;scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e,&f);
        // *b*d*f > e*c*a
        if(c == 0 && d != 0){
            puts("MEI");
            continue;
        }
        if(a == 0 && b != 0 && d != 0){
            puts("MEI");
            continue;
        }
        puts(b*d*f > e*c*a ? "MEI":"FON");
    }
    return 0;
}

B

考虑倒着做求出每个操作被执行了多少次,一个操作 $2$ 相当于将区间内的操作次数都加上这个操作的操作次数,由于操作和询问都是单调向前的,所以可以用差分解决。

然后操作 $1$ 也可以用差分解决。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;
const int ha = 1e9 + 7;

inline void add(int &x,int y){
    x += y;if(x >= ha)x -= ha;
}
int n,q;

int opt[MAXN],l[MAXN],r[MAXN];
int cf[MAXN],ans[MAXN];

int main(){
    scanf("%d%d",&n,&q);
    FOR(i,1,q) scanf("%d%d%d",opt+i,l+i,r+i);
    int now = 1;
    ROF(i,q,1){
        add(now,cf[i]);
        // DEBUG(now);
        if(opt[i] == 1){
            add(ans[l[i]],now);
            add(ans[r[i]+1],ha-now);
        }
        else{
            add(cf[l[i]-1],ha-now);
            add(cf[r[i]],now);
        }
    }
    FOR(i,1,n) add(ans[i],ans[i-1]);
    FOR(i,1,n) printf("%d%c",ans[i]," \n"[i==n]);
    return 0;
}

C

考虑斯特林公式:

$$ \begin{aligned} \sum_{S \subseteq V} f(S)^k = \sum_{i=0}^k \left\{^k_i\right\} f(S)^{\underline k} \end{aligned} $$

所以相当于要对于 $k=1\ldots 3$,计算出从所有图中有序选出 $k$ 条边的方案数。

我们枚举这个边的 $k$ 元组,相当于要计算有多少个图包含它,设这个组总共有 $x$ 个端点,那么方案数就是 $2^{n-x}$。所以我们相当于要对所有可能的点数都计数。

发现 $k=1$ 时,答案就是 $m2^{n-1}$。

发现 $k=2$ 时,情况只有一条长度为 $2$ 的链(长度表示边数)和两个端点不交的边,点数分别是 $3,4$。链可以通过枚举中心点解决,剩下那种情况可以容斥。

发现 $k=3$ 是,情况有五种:

分别计算即可。

具体说一下我是咋算的:首先情况 $5$ 就是三元环计数,将边重定向为度数小的点向度数大的点连边,如果度数相同就按照编号连边,然后对于每个点,暴力遍历能到达的点打标记,再暴力遍历能到达的点的相邻的点,有标记答案就加一,复杂度是 $O(m\sqrt m)$ 的。

然后情况 $4$ 我们考虑枚举与端点距离为 $1$ 的点,然后先算出来以这个为中心的长度为 $2$ 的链有多少个,对于每种可能我们都随便选某个端点的相邻的边作为另一条边,设点的度数为 $deg_v$,那么答案就是

$$ \sum_{x=1}^m \sum_{y=x+1}^m (deg_x+deg_y-2) = \sum_{x=1}^m (deg_v-1)(deg_x-1) $$

就可以 $O(m)$ 的去算了,但是会多算情况 $5$,对于每一个三元环都会被算 $6$ 遍,减去后发现每条链都会被算 $2$ 遍。

情况 $1$ 就是 $\sum_i \binom {deg_i}{3}$。

情况 $3$ 可以先枚举长度为 $2$ 的链的中心,然后要求第三条边不能和中心相连,发现这样可能多算了 $3$ 遍三元环,和 $2$ 遍长度为 $3$ 的链,减掉就行。

补集转化就可以算出情况 $2$,对应加起来就行。

注意这里斯特林公式不能直接加上 $k=2$ 的答案。。需要加恰好选两条不同边的方案。。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
const int ha = 1e9 + 7;
const int inv2 = 500000004;

inline char nc(){
    #define SIZE 1000000+3
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
    #undef SIZE
}

template <typename T>
inline void read(T &x){
    x = 0;int flag = 0;char ch = nc();
    while(!isdigit(ch)){
        if(ch == '-') flag = 1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
}

struct Edge{
    int u,v;
    Edge(int u=0,int v=0) : u(u),v(v) {}
}e[MAXN];
int n,m,k;
int fac[MAXN],inv[MAXN],pw[MAXN];

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
    pw[0] = 1;FOR(i,1,MAXN-1) pw[i] = 2ll*pw[i-1]%ha;
}

inline int C(int n,int m){
    if(n < 0 || m < 0 || n < m) return 0;
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

namespace BF{
    int cnt[MAXN],now;

    inline bool check(){
        return n <= 300 && m <= 300;
    }

    inline void ins(int x){
        if(!cnt[x]) now++;
        ++cnt[x];
    }

    inline void del(int x){
        if(cnt[x] == 1) now--;
        --cnt[x];
    }

    int ans,cc = 0;
    int vis[MAXN];

    inline void dfs(int step,int fg=0){
        if(step == k+1){
            add(ans,pw[n-now]);
            return;
        }
        FOR(i,1,m){
            ins(e[i].u);ins(e[i].v);
            vis[i]++;
            dfs(step+1,fg+(vis[i]==1));
            vis[i]--;
            del(e[i].u);del(e[i].v);
        }
    }

    inline void Solve(){
        dfs(1);
        printf("%d\n",ans);
        // DEBUG(cc);
        exit(0);
    }
}

namespace Subtask1{
    inline bool check(){
        return k == 1;
    }

    inline int Solve(){
        return 1ll*m*pw[n-2]%ha;
    }
}

int deg[MAXN];

namespace Subtask2{
    inline bool check(){
        return k == 2;
    }

    inline int Solve(){
        int gx1 = 0;
        FOR(i,1,m) add(gx1,m-deg[e[i].u]-deg[e[i].v]+1);
        int gx2 = 1ll*m*(m-1)%ha;
        add(gx2,ha-gx1);
        int ans = 0;
        add(ans,1ll*gx1*pw[n-4]%ha);
        add(ans,1ll*gx2*pw[n-3]%ha);
        add(ans,1ll*m*pw[n-2]%ha);
        return ans;
    }
}

namespace Subtask3{
    inline bool check(){
        return k == 3;
    }

    std::vector<int> G[MAXN];
    int gx0,gx1,gx2,gx3,gx4;
    bool vis[MAXN];

    inline int gao(){
        int res = 0;
        FOR(u,1,n){
            for(auto v:G[u]) vis[v] = 1;
            for(auto v:G[u]) for(auto w:G[v]) if(vis[w]) res++;
            for(auto v:G[u]) vis[v] = 0;
        }
        return res;
    }

    inline int Solve(){
        FOR(i,1,m){
            if(e[i].u > e[i].v) std::swap(e[i].u,e[i].v);
            if(deg[e[i].u] <= deg[e[i].v]) G[e[i].u].pb(e[i].v);
            else G[e[i].v].pb(e[i].u);
        }
        gx0 = gx1 = gx2 = gx3 = gx4 = 0;
        FOR(i,1,n) add(gx0,C(deg[i],3));
        gx4 = gao();
        FOR(i,1,n) G[i].clear();
        FOR(i,1,m) G[e[i].u].pb(e[i].v),G[e[i].v].pb(e[i].u);
        FOR(v,1,n){
            int s = 0;
            for(auto x:G[v]) add(s,deg[x]-1);
            s = 1ll*s*(deg[v]-1)%ha;
            add(gx3,s);
        }
        add(gx3,ha-6ll*gx4%ha);
        gx3 = 1ll*gx3*inv2%ha;
        FOR(v,1,n){
            int s = 1ll*C(deg[v],2)*(m-deg[v])%ha;
            add(gx2,s);
        }
        add(gx2,ha-3ll*gx4%ha);
        add(gx2,ha-2ll*gx3%ha);
        gx1 = C(m,3);
        add(gx1,ha-gx0);
        add(gx1,ha-gx2);
        add(gx1,ha-gx3);
        add(gx1,ha-gx4);
        int ans = 0;
        if(gx0) add(ans,1ll*gx0*pw[n-4]%ha);
        if(gx1) add(ans,1ll*gx1*pw[n-6]%ha);
        if(gx2) add(ans,1ll*gx2*pw[n-5]%ha);
        if(gx3) add(ans,1ll*gx3*pw[n-4]%ha);
        if(gx4) add(ans,1ll*gx4*pw[n-3]%ha);
        ans = 1ll*ans*fac[3]%ha;
        add(ans,3ll*Subtask2::Solve()%ha);
        add(ans,ha-2ll*Subtask1::Solve()%ha);
        return ans;
    }
}

std::mt19937 g(time(NULL));
std::map<P,int> S; 

int main(){
    prework();
    read(n);read(m);read(k);
    // FOR(i,1,m) ++deg[e[i].u],++deg[e[i].v]; 
    FOR(i,1,m) read(e[i].u),read(e[i].v),++deg[e[i].u],++deg[e[i].v];
    if(BF::check()) BF::Solve();
    else if(Subtask1::check()) printf("%d\n",Subtask1::Solve());
    else if(Subtask2::check()) printf("%d\n",Subtask2::Solve());
    else if(Subtask3::check()) printf("%d\n",Subtask3::Solve());
    return 0;
}
Last modification:July 11th, 2022 at 06:09 pm
如果觉得我的文章对你有用,请随意赞赏