php抽奖网站源码,外链生成器,创建网站的代码,c++网站开发https://arc101.contest.atcoder.jp/tasks/arc101_c 题解是也是dp#xff0c;好像是容斥做的#xff0c;但是看不懂#xff0c;而且也好像没讲怎么变n^2#xff0c;看了写大佬的代码#xff0c;自己理解了一下 #include bits/stdc.h
#include ext/pb_ds/assoc… https://arc101.contest.atcoder.jp/tasks/arc101_c 题解是也是dp好像是容斥做的但是看不懂而且也好像没讲怎么变n^2看了写大佬的代码自己理解了一下 #include bits/stdc.h
#include ext/pb_ds/assoc_container.hpp
using namespace __gnu_pbds;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define SZ(X) (X.size())
#define mst(a,b) memset((a),(b),sizeof(a))
#define lowbit(a) ((a)(-a))
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
typedef long long ll;
typedef pairint, int pii;
typedef pairLL, LL pll;
const int mod1e97;
const int inf 0x3f3f3f3f;
const ll INF 0x3f3f3f3f3f3f3f3f;
const int maxn5500;
inline int add(int x,int y){if((xy)mod)x-mod;return x;
}
inline int mul(int x,int y){return (ll)x*y%mod;
}
inline int sub(int x,int y){if((x-y)0)xmod;return x;
}
int ci[maxn];
vectorintto[maxn];
int dp[maxn][maxn];//dp[pos][i] 子树,有i个点未匹配的合法方案//除了根之外的子树自匹配完是不合法的,所以-dp[pos][0]表示以pos为根的子树匹配完,但pos之下子树各自之间未匹配完
int sz[maxn],uu[maxn];
void dfs(int pos,int fa){sz[pos]1;dp[pos][1]1;for(int d:to[pos])if(d!fa){dfs(d,pos);for(int i0;isz[pos]sz[d];i)uu[i]0;for(int i0;isz[pos];i)for(int j0;jsz[d];j)uu[ij]add(uu[ij],mul(dp[pos][i],dp[d][j]));sz[pos]sz[d];for(int i0;isz[pos];i)dp[pos][i]uu[i];}for(int i2;isz[pos];i2)dp[pos][0]sub(dp[pos][0],mul(dp[pos][i],ci[i]));
}
int main() {
#ifdef localfreopen(in.txt, r, stdin);
#endif // localios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ci[0]1;for(int i2;imaxn;i2)ci[i]mul(ci[i-2],i-1);int n;cinn;for(int i1;in;i){int a,b;cinab;to[a].push_back(b);to[b].push_back(a);}dfs(1,0);cout(mod-dp[1][0]);return 0;
} 转载于:https://www.cnblogs.com/bibibi/p/9542644.html
