Counting Stars 2023“钉耙编程”中国大学生算法设计超级联赛（5）hdu7335

Problem - 7335

题目大意：如果一个点连接着k个点，就称这k+1个点构成k星图，现给出一个大小为n的图，问2星图的数量^3星图的数量^...^n星图的数量是多少

3<=n<=1e6;1<=m<=1e6

思路：因为边数总共不超过1e6，所以可以遍历点，遍历度数，因为不同星图数量直接要求异或，所以对于每个点，只能求出它对每个星图的贡献，最后再求异或和

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
const int N = 1e6 + 5;
ll inv[N], fac[N];
ll C(ll x, ll y)
{//C(x,y)=y!/((y-x)!x!)return fac[y] * inv[x] % MOD * inv[y - x] % MOD;
}
ll d[N];
ll cnt[N];
ll qpow(ll a, ll b)
{//快速幂ll ret = 1;while (b){if (b & 1){ret = ret * a % MOD;}a = a * a % MOD;b >>= 1;}return ret;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;fac[0] = 1;inv[0] = 1;for (ll i = 1; i <= 1000000; i++){//预处理阶乘和阶乘逆元fac[i] = (fac[i - 1] * i) % MOD;inv[i] = qpow(fac[i], MOD - 2);}while (t--){int n, m;cin >> n >> m;for (int i = 1; i <= n; i++){d[i] = cnt[i] = 0;}for (int i = 1; i <= m; i++){int u, v;cin >> u >> v;d[u]++;d[v]++;}for (int i = 1; i <= n; i++){for (int j = 2; j <= d[i]; j++){cnt[j] = (cnt[j] + C(j, d[i])) % MOD;//第i个点对j星图的贡献}}ll ans = 0;for (int j = 2; j <= n; j++){ans = ans ^ cnt[j];}cout << ans << endl;}return 0;
}