250 想想就发现规律了。
500 暴力,括号匹配。
1000
给一个f数组,如果i存在,那么f[i]也得存在,问这样的集合有多少种。
先拓扑一下,dp[i] = mul(dp[son]+1)最后环里面的元素的乘积是结果。
#include <iostream> #include <cstdio> #include <string> #include <algorithm> #include <stdlib.h> #include <vector> #include <cmath> #include <queue> #include <set> #include <stack> using namespace std; #define LL long long int p[51][51],o[51],flag[51],nt[51]; LL dp[51]; LL temp; void dfs(int x) { flag[x] = 1; temp *= dp[x]; if(flag[nt[x]] == 1) return ; flag[nt[x]] = 1; dfs(nt[x]); } class InvariantSets { public : LL countSets(vector <int> f) { int i,j,n,z; LL ans = 1; n = f.size(); for(i = 0;i < n;i ++) { p[i][f[i]] = 1; dp[i] = 1; nt[i] = f[i]; o[f[i]] ++; } for(;;) { z = 0; for(i = 0;i < n;i ++) { if(o[i] == 0&&!flag[i]) { flag[i] = 1; z = 1; for(j = 0;j < n;j ++) { if(p[i][j] == 1&&!flag[j]) { dp[j] *= (dp[i] + 1); o[j] --; } } } } if(!z) break; } for(i = 0;i < n;i ++) { temp = 1; if(flag[i] == 0) { dfs(i); ans *= (temp+1); } } return ans; } };
原文:http://www.cnblogs.com/naix-x/p/3876201.html