http://codeforces.com/contest/568/problem/B

題意就是給一個有n個元素的集合，現在需要求有多少個A的二元關系p，使得p是對稱的，是傳遞的，但不是自反的。

首先只用(x1, x1), (x2, x2).....這種二元對形成的傳遞，對稱，非自反的滿足條件的方法數為2^n - 1（每一對可以選擇出現或者不出現，全部出現的情況是自反的，所以減掉1）

?

其次，由于如果存在(a, b)a!=b的二元關系對，那么a，b這兩個元素一定在某一個環中（根據對稱一定有(b, a)又根據傳遞一定有(a, a)與(b, b)），那么答案就是求不是每個點都在某一個環中的方法數，那么這時把某一個環看成是一個集合。設G[i]表示i個點形成若干個集合的方法數，再令F[i][j]表示i個點形成j個集合的方法數，那么G[i] = sigma(F[i][j] | j <= i/2)，下面計算F[i][j]:

　　　　　　F[i][j] = F[i - 1][j] * j + F[i - 2][j - 1] * (i - 1)

就是指第i個元素可以放在之前的某一個集合中，也可以與之前的某一個元素形成個數為2的集合

?

在算出G[i]后，來統計答案，這時候需要枚舉有多少個(x, x)這樣的二元對，設為i個，那么剩下的點就有n-i個，剩下的點可以選擇j個(2 <= j <= n - i)來形成若干個集合來與i個(x, x)的數對形成一個合法的答案。那么這里合法的大案數量就是

　　　　　　sigma(C[n][i] * sigma(C[n - i][j] * G[j]))其中，1<=i<=n-2 ?2<=j<=n-i ? C為組合數

?

?

?

?

#include <map> #include <set> #include <stack> #include <queue> #include <cmath> #include <ctime> #include <vector> #include <cstdio> #include <cctype> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; #define INF 0x3f3f3f3f #define inf (-((LL)1<<40)) #define lson k<<1, L, mid #define rson k<<1|1, mid+1, R #define mem0(a) memset(a,0,sizeof(a)) #define mem1(a) memset(a,-1,sizeof(a)) #define mem(a, b) memset(a, b, sizeof(a)) #define FIN freopen("in.txt", "r", stdin) #define FOUT freopen("out.txt", "w", stdout) #define rep(i, a, b) for(int i = a; i <= b; i ++) #define dec(i, a, b) for(int i = a; i >= b; i --)//typedef __int64 LL; typedef long long LL; const int MAXN = 4002; const int MAXM = 110000; const double eps = 1e-12; const double PI = 4.0 * atan(1.0); const int MOD = 1000000007;LL F[MAXN], C[MAXN][MAXN];void initF(int n) {F[2] = C[2][1] = 1;rep (i, 3, n) {F[i] = C[i][1] = 1;rep (j, 2, i / 2) {//C[i][j]表示i個點形成j個集合（環）的方案數C[i][j] = ( C[i - 1][j] * j % MOD + (i - 1) * C[i - 2][j - 1] % MOD ) % MOD;F[i] = ( F[i] + C[i][j] ) % MOD; //F[i]表示i個點形成若干個集合（環）的方案數}} }void initC(int n) {mem0(C);C[0][0] = 1;rep (i, 1, n) {C[i][0] = C[i][i] = 1;rep (j, 1, n - 1) //C[i][j]為組合數C[i][j] = ( C[i - 1][j - 1] + C[i - 1][j] ) % MOD;} }int main() { #ifndef ONLINE_JUDGEFIN; // FOUT; #endif // ONLINE_JUDGEinitF(4001);initC(4001);int n;while(cin >> n) {LL ans = 1;//首先計算2^n - 1rep (i, 1, n) ans = ans * 2 % MOD;ans = (ans - 1 + MOD) % MOD;//sigma(C[n][i] * sigma(C[n - i][j] * G[j]))rep (i, 1, n - 2) {int m = n - i;LL S = 0;rep (j, 2, m) {S = ( S + C[m][j] * F[j] ) % MOD;}ans = (ans + S * C[n][i]) % MOD;}cout << ans << endl;}return 0; }

轉載于:https://www.cnblogs.com/gj-Acit/p/4738190.html

總結

以上是生活随笔為你收集整理的codeforces315Div1 B Symmetric and Transitive的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。