精华内容
下载资源
问答
  • 题目链接: hiho1087 题目详解: 题目详解 代码: #include #include #include #define maxn 20 using namespace std; int next_all[maxn]={0}; int pos[1]; int dp[maxn][1]; int

    题目链接:

    hiho1087




    题目详解:

    题目详解






    代码:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #define maxn 20
    using namespace std;
    int next_all[maxn]={0};
    int pos[1<<maxn];
    int dp[maxn][1<<maxn];
    int n,ans=0;
    
    int dfs(int loc,int remain)
    {
        if(dp[loc][remain]!=-1)
            return dp[loc][remain];
        if(!remain)
            return dp[loc][remain]=next_all[loc]&1;
    
        int d=remain&next_all[loc];
        dp[loc][remain]=0;
        while(d)
        {
            int v=d&(-d);
            int remain2=remain-v;
            dp[loc][remain]+=dfs(pos[v],remain-v);
            d-=v;
        }
        return dp[loc][remain];
    }
    
    int main()
    {
    //    freopen("in.txt","r",stdin);
        int m,a,b;
        scanf("%d%d",&n,&m);
        memset(dp,-1,sizeof(dp));
        for(int i=0;i<n;i++)
            pos[1<<i]=i+1;
        while(m--)
        {
            scanf("%d%d",&a,&b);
            next_all[a]=next_all[a]|(1<<b-1);
        }
        dfs(1,(1<<n)-2);
        printf("%d\n",dp[1][(1<<n)-2]);
        return 0;
    }
    



    展开全文
  • 要考虑所有竞赛图的哈密顿回路数量之和,反过来考虑对于所有哈密顿回路,出现某回路的图的数量之和。显然对于一个回路,包含它的竞赛图数量是2n(n−3)22n(n−3)22^{\frac{n(n-3)}{2}},而一个哈密顿回路实际...

    测试地址:射命丸文的笔记
    做法:本题需要用到多项式求逆。
    首先,要求存在哈密顿回路的竞赛图的哈密顿回路期望数量,就是用哈密顿回路的总数除以存在哈密顿回路的竞赛图数量。
    要考虑所有竞赛图的哈密顿回路数量之和,反过来考虑对于所有哈密顿回路,出现某回路的图的数量之和。显然对于一个回路,包含它的竞赛图数量是2n(n3)2,而一个哈密顿回路实际上就是一个1~n的圆排列,共有n!n=(n1)!种,于是我们就得到了答案:(n1)!2n(n3)2
    那么接下来就是求存在哈密顿回路的竞赛图数量了。令f(n)n个点的合法竞赛图数量,再令g(n)n个点的竞赛图数量,显然g(n)=2Cn2。我们知道,一个竞赛图存在哈密顿回路当且仅当该竞赛图强连通,因此合法竞赛图的数量就是强连通的竞赛图的数量。因此我们得到下面的式子:
    g(n)=i=1nCnif(i)g(ni)
    上面式子的含义,可以看做我们在枚举拓扑序最小的强连通分量,该强连通分量内所有的点向所有其他点连边,这样就可以不重不漏地统计竞赛图了。
    将组合数拆开,化成下面的形式:
    g(n)n!=i=1nf(i)i!g(ni)(ni)!
    F(x)f(i)i!的生成函数,G(x)g(i)i!的生成函数,则有:
    G(x)=F(x)G(x)+1
    所以:
    F(x)=G(x)1G(x)
    用多项式求逆即可在O(nlogn)的时间复杂度内解决问题。
    以下是本人代码:

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll mod=998244353;
    const ll G=3;
    int n,rev[400010];
    ll fac[100010],g[400010],s[400010]={0},p[400010]={0};
    
    ll power(ll a,ll b)
    {
        ll s=1,ss=a;
        b=(b%(mod-1)+(mod-1))%(mod-1);
        while(b)
        {
            if (b&1) s=s*ss%mod;
            ss=ss*ss%mod;b>>=1;
        }
        return s;
    }
    
    void NTT(ll *a,int n,ll type)
    {
        for(int i=0;i<=n;i++)
            if (i<rev[i]) swap(a[i],a[rev[i]]);
        for(int mid=1;mid<n;mid<<=1)
        {
            ll W=power(G,type*(mod-1)/(mid<<1));
            for(int l=0;l<n;l+=(mid<<1))
            {
                ll w=1;
                for(int k=0;k<mid;k++,w=w*W%mod)
                {
                    ll x=a[l+k],y=w*a[l+mid+k]%mod;
                    a[l+k]=(x+y)%mod;
                    a[l+mid+k]=(x-y+mod)%mod;
                }
            }
        }
        if (type==-1)
        {
            ll inv=power(n,mod-2);
            for(int i=0;i<n;i++)
                a[i]=a[i]*inv%mod;
        }
    }
    
    int calc_rev(int limit)
    {
        int x=1,bit=0;
        while(x<=limit) bit++,x<<=1;
        rev[0]=0;
        for(int i=1;i<x;i++)
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
        return x;
    }
    
    void calc_inv(int len)
    {
        if (len==1)
        {
            s[0]=power(g[0],mod-2);
            return;
        }
        calc_inv((len+1)>>1);
    
        int x=calc_rev(len<<1);
        for(int i=0;i<len;i++)
            p[i]=g[i];
        for(int i=len;i<=x;i++)
            p[i]=0;
        NTT(p,x,1),NTT(s,x,1);
        for(int i=0;i<=x;i++)
            s[i]=((2ll*s[i]-p[i]*s[i]%mod*s[i])%mod+mod)%mod;
        NTT(s,x,-1);
        for(int i=len;i<=x;i++)
            s[i]=0;
    }
    
    int main()
    {
        scanf("%d",&n);
        fac[0]=1;
        for(ll i=1;i<=n;i++)
            fac[i]=fac[i-1]*i%mod;
    
        for(ll i=0;i<=n;i++)
            g[i]=power(2ll,i*(i-1ll)/2ll)*power(fac[i],mod-2)%mod;
        calc_inv(n+1);
    
        g[0]=0;
        int x=calc_rev(n<<1);
        NTT(g,x,1),NTT(s,x,1);
        for(int i=0;i<=x;i++)
            g[i]=g[i]*s[i]%mod;
        NTT(g,x,-1);
        for(ll i=1;i<=n;i++)
        {
            if (i<=2)
            {
                if (i==1) printf("1\n");
                else printf("-1\n");
            }
            else
            {
                g[i]=g[i]*fac[i]%mod;
                printf("%lld\n",fac[i-1]*power(2ll,i*(i-3ll)/2ll)%mod*power(g[i],mod-2)%mod); 
            }
        }
    
        return 0; 
    }
    展开全文
  • 这个期望就是所有竞赛图的哈密顿回路数量/存在哈密顿回路的竞赛图的数量。 前面那个挺好做,考虑每条哈密顿回路的贡献,就是(n−1)!∗2n(n−1)2−n(n−1)!∗2n(n−1)2−n(n-1)!*2^{\frac{n(n...

    题意:

    给出n,求对于任意的1in,求在所有i个点且有哈密顿回路的竞赛图中,哈密顿回路的期望数量是多少。答案模998244353。

    题解:

    这个期望就是所有竞赛图的哈密顿回路数量/存在哈密顿回路的竞赛图的数量。
    前面那个挺好做,考虑每条哈密顿回路的贡献,就是(n1)!2n(n1)2n
    那么就是要找存在哈密顿回路的竞赛图的数量。
    有一个结论,竞赛图的一个强连通分量一定能找到一个简单环。
    所以就是求强联通的竞赛图个数。而将一个竞赛图强联通缩点后显然是一条链。
    考虑容斥,枚举这条链最下面的的scc的大小,于是得到式子:
    h(n)=2Cn2

    f(n)=h(n)k=1n1f(k)h(nk)Cnk

    将组合数展开,求逆一波即可。
    code:

    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #define LL long long
    using namespace std;
    const LL p=998244353,yg=3;
    LL bin[400000],a[400000],b[400000],c[400000],h[400000];
    LL pow(LL a,LL b)
    {
        LL ans=1;
        while(b)
        {
            if(b&1) ans=ans*a%p;
            a=a*a%p;b>>=1;
        }
        return ans;
    }
    void ntt(LL *a,LL n,LL op)
    {
        for(LL i=0;i<n;i++) bin[i]=(bin[i>>1]>>1)|((i&1)*(n>>1));
        for(LL i=0;i<n;i++) if(i<bin[i]) swap(a[i],a[bin[i]]);
        for(LL i=1;i<n;i<<=1)
        {
            LL wn=pow(yg,op==1?(p-1)/(i<<1):p-1-(p-1)/(i<<1)),t,w;
            for(LL j=0;j<n;j+=i<<1)
            {
                w=1;
                for(LL k=0;k<i;k++)
                {
                    t=a[j+i+k]*w%p;w=w*wn%p;
                    a[i+j+k]=(a[j+k]-t+p)%p;a[j+k]=(a[j+k]+t)%p;
                }
            }
        }
        if(op==-1)
        {
            LL Inv=pow(n,p-2);
            for(LL i=0;i<n;i++) a[i]=a[i]*Inv%p;
        }
    }
    void pol_inv(LL deg,LL *a,LL *b)
    {
        if(deg==1) {b[0]=pow(a[0],p-2);return;}
        pol_inv((deg+1)>>1,a,b);
        LL N=1;while(N<deg<<1) N<<=1;
        copy(a,a+deg,c);fill(c+deg,c+N,0);
        ntt(c,N,1);ntt(b,N,1);
        for(LL i=0;i<N;i++)
        {
            b[i]=(2-b[i]*c[i]%p)*b[i]%p;
            b[i]+=b[i]<0?p:0;
        }
        ntt(b,N,-1);fill(b+deg,b+N,0);
    }
    LL fac[100010],inv[100010];
    void pre()
    {
        fac[0]=fac[1]=inv[0]=inv[1]=1;
        for(LL i=2;i<=100000;i++) fac[i]=fac[i-1]*i%p,inv[i]=(p-p/i)*inv[p%i]%p;
        for(LL i=2;i<=100000;i++) inv[i]=inv[i-1]*inv[i]%p;
    }
    LL n;
    LL calc(LL n) {return n<2?0:(n)*(n-1)/2;}
    int main()
    {
        scanf("%lld",&n);
        pre();
        for(LL i=1;i<=n;i++) a[i]=h[i]=pow(2,calc(i))*inv[i]%p;
        a[0]=1;pol_inv(n+1,a,b);
        LL N=1;while(N<(n+1)<<1) N<<=1;
        ntt(b,N,1);ntt(h,N,1);
        for(LL i=0;i<N;i++) b[i]=b[i]*h[i]%p;
        ntt(b,N,-1);
        puts("1");
        for(LL i=2;i<=n;i++)
        {
            if(!b[i]) puts("-1");
            else printf("%lld\n",fac[i-1]*pow(2,calc(i)-i)%p*pow(b[i]%p*fac[i]%p,p-2)%p);
        }
    }
    展开全文
  • P4233 射命丸文的笔记

    2019-04-20 19:06:00
    求选取的竞赛图中哈密顿回路数量的期望值 由于答案可能过大/丢失精度,只需要输出答案除以998244353的余数 题解 总回路数量/有回路的竞赛图数量 总回路数量:统计贡献 有回路的数量: 即强连通...

    P4233 射命丸文的笔记

    官方题解

    题意

    如果一个竞赛图含有哈密顿回路,则称这张竞赛图为值得记录的

    从所有含有n个顶点(顶点互不相同)的,值得记录的竞赛图中等概率随机选取一个

    求选取的竞赛图中哈密顿回路数量的期望值

    由于答案可能过大/丢失精度,只需要输出答案除以998244353的余数

    题解

    总回路数量/有回路的竞赛图数量

    总回路数量:统计贡献

    有回路的数量:

    即强连通!

    枚举缩点之后最小的强连通分量(这样和别的连通分量的边的方向是固定的!)

    多项式求逆

     

    注意:

    1.求Inv时候,f[0]=1其实

    2.乘法,长度是2*lp

    3.C(n,2)爆int ,快速幂时候注意

    // luogu-judger-enable-o2
    #include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;
        while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);
        (fl==true)&&(x=-x);
    }
    template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    
    namespace Miracle{
    const int N=1e5+5;
    const int mod=998244353;
    const int G=3;
    const int GI=332748118;
    int n;
    int f[4*N],g[4*N];
    int rev[4*N];
    int jie[N],inv[N];
    int ad(int x,int y){
        return x+y>=mod?x+y-mod:x+y;
    }
    int qm(int x,ll y){
        int ret=1;
        while(y){
            if(y&1) ret=(ll)ret*x%mod;
            x=(ll)x*x%mod;
            y>>=1;
        }
        return ret;
    }
    void NTT(int *f,int n,int c){
        for(reg i=0;i<n;++i){
            if(i<rev[i]) swap(f[i],f[rev[i]]);
        }
        for(reg p=2;p<=n;p<<=1){
            int gen;
            int len=p/2;
            if(c==1) gen=qm(G,(mod-1)/p);
            else gen=qm(GI,(mod-1)/p);
            for(reg l=0;l<n;l+=p){
                int buf=1;
                for(reg k=l;k<l+len;++k){
                    int tmp=(ll)f[k+len]*buf%mod;
                    f[k+len]=(f[k]-tmp+mod)%mod;
                    f[k]=(f[k]+tmp)%mod;
                    buf=(ll)buf*gen%mod;
                }
            }
        }
        if(c==-1){
            int iv=qm(n,mod-2);
            for(reg i=0;i<n;++i) f[i]=(ll)f[i]*iv%mod;
        }
    }
    int p[4*N],ni[4*N];
    void Inv(int *f,int *g,int n){
        if(n==1){
            g[0]=1;return;
        }
        Inv(f,g,n>>1);
        for(reg i=1;i<n;++i) p[i]=f[i];
        p[0]=1;
        for(reg i=n;i<2*n;++i) p[i]=0;
        for(reg i=0;i<2*n;++i){
            rev[i]=rev[i>>1]>>1|((i&1)?n:0);
        }
        NTT(p,2*n,1);NTT(g,2*n,1);
        for(reg i=0;i<2*n;++i){
            g[i]=(ll)((ll)2-(ll)g[i]*p[i]%mod+mod)%mod*g[i]%mod;
        }
        NTT(g,2*n,-1);
        for(reg i=n;i<2*n;++i) g[i]=0;
    }
    int main(){
        rd(n);
        jie[0]=1;
        for(reg i=1;i<=n;++i) jie[i]=(ll)jie[i-1]*i%mod;
        inv[n]=qm(jie[n],mod-2);
        for(reg i=n-1;i>=0;--i) inv[i]=(ll)inv[i+1]*(i+1)%mod;
        for(reg i=1;i<=n;++i){
            g[i]=(ll)qm(2,(ll)i*(i-1)/2)*inv[i]%mod;
        }
        int lp=1;
        for(lp=1;lp<n+1;lp<<=1);
        
        Inv(g,ni,lp);
        
        lp<<=1;
        // prt(g,0,lp-1);
        // prt(ni,0,lp-1);
        for(reg i=0;i<lp;++i){
            rev[i]=(rev[i>>1]>>1)|((i&1)?lp>>1:0);
        }
        NTT(g,lp,1);
        NTT(ni,lp,1);
        for(reg i=0;i<lp;++i){
            f[i]=(ll)g[i]*ni[i]%mod;
        }
        NTT(f,lp,-1);
        // prt(f,0,lp-1);
    
    
        for(reg i=1;i<=n;++i){
            f[i]=(ll)f[i]*jie[i]%mod;
            // cout<<" i "<<f[i]<<endl;
            if(i==1) puts("1");
            else if(i==2) puts("-1");
            else{
                int tot=(ll)jie[i-1]*qm(2,(ll)i*(i-1)/2-i)%mod;
                printf("%d\n",(ll)tot*qm(f[i],mod-2)%mod);
            }
        }
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
       Date: 2019/4/13 19:58:12
    */

     

    转载于:https://www.cnblogs.com/Miracevin/p/10742151.html

    展开全文
  • 求所有\(n\)个点带标号强连通竞赛图中哈密顿回路数量的平均值. 题解 因为要求平均数,所以我们可以把分母和分子单开来算。 \(n\)个点的所有竞赛图的所有哈密顿回路个数是可以求出来的,就是可以枚举所有哈密顿回路,...
  • 求选取的竞赛图中哈密顿回路数量的期望 输出答案除以998244353998244353998244353的余数 竞赛图:指任意两个顶点间恰有一条有向边的有向图 哈密顿回路:指除起点和终点外经过所有顶点恰好一次且起点和终点相同的...
  • 题意 给出n,求对于任意的1≤i≤n1≤i≤n1\le i\le n,求在所有i...所有竞赛图的哈密顿回路数量很好求,考虑每一条哈密顿路径的贡献,那么答案就是(n−1)!∗2n(n−1)2−n(n−1)!∗2n(n−1)2−n(n-1)!*2^{\frac{n(n...
  • 分析:这道题非常直接的做法就是DFS搜索了,我们可以从任一顶点出发,不走重复点,若能回到顶点,那么哈密顿回路数量+1。但是直接暴力搜会超时,所以需要加上一个位运算的优化。 位运算搜索: 将邻接链表压缩成一个...
  • 【插头DP】Tony's Tour

    2012-04-20 09:36:18
    这样做就可以不求哈密顿路径数量,而求哈密顿回路数量,要简单得多。陈丹琦神牛的文章里介绍的方法。 然后就和Formula 1一模一样了。 因为n要增大4,m要增大2,所以我一开始map[10][10]小了。 然后又没有用...
  • 【题意】给定n*m个方格图,有一些障碍格,求非障碍格的哈密顿回路数量。n,m<=12。 【算法】插头DP 【题解】《基于连通性状态压缩的动态规划问题》 by CDQ(万恶之源T_T) 如果你想学最小表示法,当然首推...
  • hiho一下 第六十三周

    千次阅读 2015-09-29 00:19:52
    题意分析给定一个有向图,求图中哈密顿回路数量。算法分析哈密顿回路,具体到本题中即从某一个点开始经过所有的点一次后再回到该点的不同路径数。对于这个不同需要注意两点: 如果我们将路径经过的点按顺序写下,...
  • 给定一个有向图,求图中哈密顿回路数量。 算法分析 哈密顿回路,具体到本题中即从某一个点开始经过所有的点一次后再回到该点的不同路径数。对于这个不同需要注意两点: 如果我们将路径经过的点按顺序写...
  • 给定一个有向图,求图中哈密顿回路数量哈密顿回路,具体到本题中即从某一个点开始经过所有的点一次后再回到该点的不同路径数。对于这个不同需要注意两点: 如果我们将路径经过的点按顺序写下,比如当n=3时,...
  • 考虑所有竞赛图的哈密顿回路条数n!n2Cn2−n\frac {n!} {n} 2^{C_{n}^{2}-n}nn!​2Cn2​−n,即选出一条哈密顿回路剩下的边任意连。 但题目中所求的是有哈密顿回路条数的竞赛图,即强联通的竞赛图。 设f(n)f(n)f(n)...
  • 【HDU1693】Eat the Trees(插头dp) ...因为可以任意分配哈密顿回路数量,因此根本不需要再考虑插头的配对问题了,那么直接分情况转移就好啦。 #include<iostream> #include<cstdio&...
  • 题意:给 mmm 棵树,树之间是完全图,问哈密顿回路数量 我们考虑到最后的哈密顿回路一定是有一段一段的树链串起来得到的 相当于每一棵树拆分成若干条树链,大小不限个数不限,所有的拼接起来,要求相邻的不来自...
  • 对于i从1~n,输出i个点组成竞赛图中,哈密顿回路的平均数量 Solution 竞赛图存在哈密顿回路的充要条件就是强连通 设f(n)f(n)f(n)表示n个点形成强连通竞赛图的方案数,一个简单的容斥就是f(n)=2(n2)−∑i=1n−1(ni)f...
  • 离散化坑死人了 !!! 不排序就lower_bound。。。 用dijkstra跑出每一个点到其它点的距离,注意一定要加入1...可以参考之前写的哈密顿回路。 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #include
  • }{n}\)条本质不同的哈密顿回路,每一条哈密顿回路恰好会出现在\(2^{\binom{n}{2} - n}\)个图中,所以我们实际上要算的是强连通有向竞赛图的数量。 设\(f_i\)表示点数为\(i\)的强连通竞赛图数,转移考虑用总数\(2^\...
  •  啊嘞,我只会求哈密顿回路啊……这可怎么搞……  容易想到:要是把起点和重点直接连上就变成一条回路了……那么我们就连一下~  我们可以在整张图下面加两行:(例:3*5)  1 1 1 1 1  1 1 1 1 1  1 1 1 1 ...
  • 【GDOI2017第二轮模拟day1】最长路径

    千次阅读 2017-04-15 16:55:55
    题目大意给定n,求对于i=1…n,从点1出发最长简单路径长度为...证明:首先3个点的显然存在,假设k个点的存在一条哈密顿回路,那么现在加入第k+1个点,只要存在回路上相邻两个点p,q,满足p连向k+1,k+1连向q即可。如果没
  • [Link\frak{Link}Link] 给定一个1≤n≤13\frak{1\le n\le13}1≤n≤13点1≤m≤100\frak{1\le m...求权值最大的哈密顿回路(以某个点为起点,经过其他每个点一次的回路)的权值和数量。权值定义如下:  1.记V1\fr...
  • 哈密顿回路数量。n,m claris讲了插头DP,感觉都差不多听懂了,但是实现还是有一定困难,花了3个小时才写出来我的第一篇插头DP的程序。感觉就是维护一个轮廓线,每一格压位表示,然后DP过程中每一次对这个轮廓线...

空空如也

空空如也

1 2
收藏数 37
精华内容 14
关键字:

哈密顿回路数量