淘宝客网站跳转单品,成都各公司网站,全国连锁装修公司,做淘宝有哪些推广网站题目链接
CF方向 Luogu方向
题目解法
首先考虑 n n n 为奇数的情况无解#xff0c;这个可以通过乘积矛盾简单证明
接下来考虑一个结论是#xff1a;偶数个点的树的形态确定之后#xff0c;只有恰好 1 1 1 种染色方案#xff0c;即从叶子一层一层往上面染#xff0c;…题目链接
CF方向 Luogu方向
题目解法
首先考虑 n n n 为奇数的情况无解这个可以通过乘积矛盾简单证明
接下来考虑一个结论是偶数个点的树的形态确定之后只有恰好 1 1 1 种染色方案即从叶子一层一层往上面染这样一定可以构造出来解且唯一
考虑一个更强的结论是一条边的边权为 1 1 1 当且仅当这条边对应的两个子树大小都为偶数 为什么考虑 s i z siz siz 为奇数的情况一定不可能点全部合法但又要使它合法只能让子树根的乘积为 1 1 1然后令上面连向整体的边为 − 1 -1 −1 即可 s i z siz siz 全为偶数的情况用反证法不难证出
现在有一个很重要的 t r i c k trick trick我也要提醒我自己是对于每条边考虑它的贡献然后类和 这样就好算了对于一条连接大小为 i , n − i i,n-i i,n−i 的子树的边必须在 1 − n 1-n 1−n 路径上贡献为 ( n − 2 i − 1 ) f i f n − i i ( n − i ) \binom{n-2}{i-1}f_if_{n-i}i(n-i) (i−1n−2)fifn−ii(n−i) 其中 f i f_i fi 为 i i i 个点的树的形态方案数即为 i i − 2 i^{i-2} ii−2 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
#include bits/stdc.h
using namespace std;
const int N500100,P998244353;
int n,fac[N],inv[N],f[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
int qmi(int a,int b){int res1;for(;b;b1){if(b1) res1ll*res*a%P;a1ll*a*a%P;}return res;
}
int C(int a,int b){if(ab||b0) return 0;return 1ll*fac[a]*inv[b]%P*inv[a-b]%P;
}
int main(){nread();if(n1){ puts(0);exit(0);}fac[0]1;for(int i1;in;i) fac[i]1ll*fac[i-1]*i%P;inv[n]qmi(fac[n],P-2);for(int in-1;i0;i--) inv[i]1ll*inv[i1]*(i1)%P;f[1]1;for(int i2;in;i) f[i]qmi(i,i-2);int ans0;for(int i1,neg-1;in;i,neg*-1) ans(ans1ll*neg*C(n-2,i-1)*f[i]%P*f[n-i]%P*i%P*(n-i))%P;printf(%d\n,(ansP)%P);return 0;
}
