@2368860385
2020-11-07T03:06:16.000000Z
字数 5354
阅读 175
正睿停课
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>#include<cctype>#include<set>#include<vector>#include<queue>#include<map>#define fi(s) freopen(s,"r",stdin);#define fo(s) freopen(s,"w",stdout);using namespace std;typedef long long LL;inline int read() {int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;}const int N = 200100;const int mod = 1e9 + 7;LL f[N], ifac[N];LL ksm(int a,int b) {LL res = 1;while (b) {if (b & 1) res = 1ll * res * a % mod;a = 1ll * a * a % mod;b >>= 1;}return res;}void init(int n) {f[0] = 1;for (int i=1; i<=n; ++i) f[i] = 1ll * f[i - 1] * i % mod;ifac[n] = ksm(f[n], mod - 2);for (int i=n; i>=1; --i) ifac[i - 1] = 1ll * ifac[i] * i % mod;}inline LL C(int n,int m) {LL t1 = f[n], t2 = ifac[n - m], t3 = ifac[m];return 1ll * t1 * t2 % mod * t3 % mod;}inline LL Calc(int n,int m) {if (n == m && n == 1) return 1;return C(n + m - 2, n - 1);}int main() {int n = read(), m = read(), a = read(), b = read();// init(max(n, m) + 10);init(n + m);LL ans = 0;for (int i=1; i<=(n-a); ++i) {LL t1 = Calc(i, b);LL t2 = Calc(n - i + 1, m - b);(ans += (1ll * t1 * t2 % mod)) %= mod;}cout << ans;return 0;}/*2 3 1 110 7 3 4*/
推推式子，比较有趣
https://www.cnblogs.com/SovietPower/p/9839063.html
三个的还需要对度数巨大的容斥。
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>#include<cctype>#include<set>#include<vector>#include<queue>#include<map>#define fi(s) freopen(s,"r",stdin);#define fo(s) freopen(s,"w",stdout);using namespace std;typedef long long LL;inline int read() {int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;}#define Edge pair<int,int>const int N = 200005;const int mod = 1e9 + 7;int A[N], B[N], deg[N], mi[N];int n, m, k;LL ksm(int a,int b) {LL res = 1;while (b) {if (b & 1) res = 1ll * res * a % mod;a = 1ll * a * a % mod;b >>= 1;}return res;}namespace BF1{int sel[100], vis[100];LL Answer;void pd() {int cnt = 0;for (int i=1; i<=m; ++i)if (sel[A[i]] && sel[B[i]]) cnt ++;if (k == 1) (Answer += cnt) %= mod;else if (k == 2) (Answer += cnt * cnt) %= mod;else if (k == 3) (Answer += cnt * cnt * cnt) %= mod;}void dfs(int x) {if (x == n + 1) { pd(); return ; }sel[x] = 1; dfs(x + 1);sel[x] = 0; dfs(x + 1);}void Main() {dfs(1); cout << Answer;}}namespace BF2{void Main() {LL ans = 0, t = ksm(2, n - 2);ans = 1ll * t * m % mod;cout << ans;}}namespace BF3{void Main() {LL ans = 1ll * m * mi[n - 2] % mod;for (int i = 1; i <= m; ++i) {int d1 = deg[A[i]], d2 = deg[B[i]];if (n >= 3) ans = (ans + 1ll * (d1 + d2 - 2) * mi[n - 3] % mod) % mod;// 选这条边的时候，另一条边可能的方案数，(d1-1)+(d2-1)if (n >= 4) ans = (ans + 1ll * (m - d1 - d2 + 1) * mi[n - 4] % mod) % mod;// 选这条边的时候的其它边的方案数，m-(d1-1)-(d2-1)-1}cout << ans % mod;}}namespace BF4{void Main() {LL ans = 0;for (int i = 1; i <= m; ++i)for (int j = 1; j <= m; ++j)for (int k = 1; k <= m; ++k) {int T[10] = {A[i], B[i], A[j], B[j], A[k], B[k]};sort(T, T + 6);int cnt = unique(T, T + 6) - T;ans = (ans + mi[n - cnt]) % mod;}cout << ans % mod;}}int main() {n = read(), m = read(), k = read();mi[0] = 1;for (int i = 1; i <= n; ++i) mi[i] = 1ll * mi[i - 1] * 2 % mod;for (int i=1; i<=m; ++i) {A[i] = read(), B[i] = read();deg[A[i]] ++; deg[B[i]] ++;}if (n <= 25) { BF1::Main(); return 0; }if (k == 1) { BF2::Main(); return 0; }if (k == 2) { BF3::Main(); return 0; }if (k == 3) {if (m <= 300) { BF4::Main(); return 0; }}return 0;}/*4 5 21 22 33 44 12 4*/
摘自http://zhengruioi.com/submission/60594
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#define mod 1000000007#define maxn 100010#define maxm 100010using namespace std;int n,m,k,d[maxn],power2[maxn];struct edge{int u,v;}e[maxm];void init(){power2[0]=1;for(int i=1;i<maxn;++i)power2[i]=power2[i-1]*2ll%mod;memset(d,0,sizeof(d));scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;++i){scanf("%d%d",&e[i].u,&e[i].v);++d[e[i].u],++d[e[i].v];}}/*三条边部分：s3:三元环个数(三元环计数)s4:4个点(不含菊花)t4:至少两处相交(可直接算)s4=t4-s3*3s5:5个点t5:至少一处相交(可直接算)s5=t5-s4*2-s3*3s6:三条没有交的边的个数t6:至少两处没交(可以直接算)s6=(t6-s5)/3ans=菊花(可直接算)+s3+s4+s5+s6 (要乘各自的系数)*/const int size=1000007;inline bool operator == (const edge &x,const edge &y){return x.u==y.u&&x.v==y.v;}struct HASH{vector<edge>tmp[size];inline void clear(){for(int i=0;i<size;++i)tmp[i].clear();}inline void insert(int u,int v){int pos=(1ll*u*maxn+v)%size;edge e=(edge){u,v};for(int i=0;i<tmp[pos].size();++i)if(tmp[pos][i]==e)return;tmp[pos].push_back(e);}inline bool find(int u,int v){int pos=(1ll*u*maxn+v)%size;edge e=(edge){u,v};for(int i=0;i<tmp[pos].size();++i)if(tmp[pos][i]==e)return 1;return 0;}}h;vector<int>E[maxn];int count_three_circles(){h.clear();for(int i=1;i<=m;++i){int u=e[i].u,v=e[i].v;h.insert(u,v),h.insert(v,u);E[u].push_back(v),E[v].push_back(u);}int ans=0;for(int i=1;i<=m;++i){int u=e[i].u,v=e[i].v,y=d[u]<d[v]?u:v,x=u^v^y;for(int j=0;j<E[y].size();++j){int z=E[y][j];if(h.find(z,x))++ans;}}return ans/3;}int count(){int ans=0,s3=count_three_circles(),s4,t4=0,s5,t5=0,s6,t6=0;for(int i=1;i<=n;++i)if(n>=4)ans=(ans+d[i]*(d[i]-1ll)%mod*(d[i]-2)%mod*power2[n-4])%mod;if(n>=3)ans=(ans+6ll*s3*power2[n-3])%mod;for(int i=1;i<=m;++i){int u=e[i].u,v=e[i].v;t4=(t4+(d[u]-1ll)*(d[v]-1))%mod;}s4=(t4-3ll*s3)%mod;if(s4<0)s4+=mod;if(n>=4)ans=(ans+6ll*s4*power2[n-4])%mod;for(int i=1;i<=n;++i)t5=(t5+d[i]*(d[i]-1ll)/2%mod*(m-d[i]))%mod;s5=(t5-s4*2ll-s3*3ll)%mod;if(s5<0)s5+=mod;if(n>=5)ans=(ans+6ll*s5*power2[n-5])%mod;for(int i=1;i<=m;++i){int u=e[i].u,v=e[i].v,x=m-1-(d[u]+d[v]-2);t6=(t6+x*(x-1ll)/2)%mod;}s6=t6-s5;if(s6<0)s6+=mod;if(n>=6)ans=(ans+2ll*s6*power2[n-6])%mod;return ans;}void solve(){int ans=0;for(int i=1;i<=m;++i){int u=e[i].u,v=e[i].v,du=d[u],dv=d[v];ans+=power2[n-2];if(ans>=mod)ans-=mod;int k1;if(k==1)k1=0;if(k==2)k1=1;if(k==3)k1=3;if(n>=3)ans=(ans+1ll*k1*power2[n-3]*(du+dv-2))%mod;if(n>=4)ans=(ans+1ll*k1*power2[n-4]*(m-1-(du+dv-2)))%mod;}if(k==3){ans+=count();if(ans>=mod)ans-=mod;}printf("%d\n",ans);}int main(){init();solve();return 0;