题目传送门:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1806
数据生成器:http://paste.ubuntu.com/23358513/
这题知道Prufer编码的同学都能一眼秒吧?
就是裸的Prufer加上容斥。
但这题细节比较多,我说说我被坑的两个地方吧:
1)可能有多个限制条件针对一个点,在容斥的时候要排除这种情况
2)容斥的时候,所有点的度都确定了,但度数不等于n-2的情况容斥也要排除掉
#include<bits/stdc++.h> #define LL long long using namespace std; const int M = 20; const int N = 1000000+9; const int MX = 1000000; const int MOD = 1000000007; int POW[N],REV[N],lim[M],id[M],n,m,vout,vis[N]; set<pair<int,int> > S; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline int pow(int w, int t) { if (!w || t <= 0) return 1; int ret = 1; while (t) { if (t & 1) ret = (LL)ret * w % MOD; w = (LL)w * w % MOD; t >>= 1; } return ret; } inline int C(int x, int y) { int ret = (LL)POW[y] * REV[x] % MOD; return (LL)ret * REV[y-x] % MOD; } void DFS(int t, int tot, int cnt, int sol, int f) { if (tot < 0 || (tot > 0 && cnt == n)) return; else if (t >= m + 1) { if (!cnt) return; else { sol = (LL)sol * pow(n - cnt,tot) % MOD; vout = ((vout + f*sol) % MOD + MOD) % MOD; } } else { DFS(t+1, tot, cnt, sol, f); if (!vis[id[t]]) { vis[id[t]] = 1; DFS(t+1, tot - lim[t], cnt + 1, (LL)sol * C(lim[t],tot) % MOD, -f); vis[id[t]] = 0; } } } int main(){ n = read(); m = read(); for (int i=1;i<=m;i++) { id[i] = read(), lim[i] = read() - 1; if (S.count(make_pair(id[i],lim[i]))) { i--; m--; } else { S.insert(make_pair(id[i],lim[i])); } } POW[1] = REV[1] = POW[0] = REV[0] = 1; for (int i=2;i<=MX;i++) POW[i] = (LL)POW[i-1] * i % MOD; REV[MX] = pow(POW[MX], MOD - 2); for (int i=MX-1;i;i--) REV[i] = (LL)REV[i+1] * (i + 1) % MOD; vout = pow(n, n-2); DFS(1,n-2,0,1,1); printf("%d\n",vout); return 0; }