51NOD1835 完全图-白红宇

51NOD1835 完全图

阅读量：6253 次

发布时间：2019-06-22

本文共 912 字，大约阅读时间需要 3 分钟。

分析

令f(i,j)表示i点完全图有j个联通块的方案数。

讨论有i-1个点已经固定了，我们拉出一个代表元素然后讨论它的集合大小然后组合数算一下就可以了。

$$ dp(i,j) = \sum_{k=1}^{i-1} C_{i-1}^{k-1} dp(i-k,j-1) dp(k,1) $$

$$ dp(i,1) = 2^{\frac{i(i-1)}{2}} - \sum{j=2}^i dp(i,j) $$

因为至少要删一条边，所以m=1时候最终答案要减1。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const long long mod = 998244353;#define add(x,y) x=(x+y)%modlong long c[600][600],dp[600][600];inline long long pw(long long x,long long p){ long long res=1; while(p){ if(p&1)res=res*x%mod; x=x*x%mod; p>>=1; } return res;}int main(){ long long n,m,i,j,k; scanf("%lld%lld",&n,&m); c[0][0]=1; for(i=1;i<=500;i++) c[i][0]=c[i][i]=1; for(i=1;i<=500;i++) for(j=1;j