Title
Given an undirected simple graph with n (n?≥?3) vertices and m edges where the vertices are numbered from 1 to n, we call it a “sub-cycle” graph if it’s possible to add a non-negative number of edges to it and turn the graph into exactly one simple cycle of n< /em> vertices.
Given two integers n and m, your task is to calculate the number of different sub-cycle graphs with n vertices and m< /em> edges. As the answer may be quite large, please output the answer modulo 109? + ?7.
Recall that
- A simple graph is a graph with no self loops or multiple edges;
- A simple cycle of n (n?≥?3) vertices is a connected undirected simple graph with n vertices and n edges, where the degree of each vertex equals to 2;
- Two undirected simple graphs with n vertices and m edges are different, if they have different sets of edges;
- Let u < v, we denote (u,?v) as an undirected edge connecting vertices u and v. Two undirected edges (u1,?v1) and (u 2,?v2) are different, if u1?≠?u2 or v1?≠ ?v2.
input
There are multiple test cases. The first line of the input contains an integer T (about 2?×?104), indicating the number of test cases. For each test case:
The first and only line contains two integers n and m (3?≤?n?≤?105,
), indicating the number of vertices and the number of edges in the graph.
It’s guaranteed that the sum of n in all test cases will not exceed 3?×?107.
output
For each test case output one line containing one integer, indicating the number of different sub-cycle graphs with n vertices and m edges modulo 109? + ?7.
The main idea of the title
Define a simple subring graph as: a simple graph with n points and m edges. You can add a number of non-negative integer edges to turn the entire graph into a simple ring graph with n points.
Given n and m, representing a simple graph with n points and m edges, how many simple subring graphs with n points and m edges are there?
Ideas
Asub-cycle graph can be understood as each connected block being a point or a chain (obviously rings are also possible).
The following situation could be discussed:
1. 
!}{2})
You can use any point as the starting point, and then the next situation is that each point can be connected to n-1, n-2…, 1 type,
The total number is!)
3. 
4. The remaining situation is 
First enumerate the existence of i chains in China Unicom block, which is equivalent to the existence of 
)
!*\binom{m-1}{i-1})
So the overall plan is
*(m-i)!*\binom{m-1}{i-1})
#include<bits/stdc + + .h>
using namespace std;
#define int long long
const int N = 2e5 + 100;
const int mod = 1e9 + 7;
int P1[N],P2[N];
int ksm(int a,int b) {
int ans=1;
while(b) {
if(b & amp;1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
void init(int tot) {
P1[0]=1;
for(int i=1; i<=tot; i + + )P1[i]=1ll*P1[i-1]*i%mod;
P2[tot]=ksm(P1[tot],mod-2);
for(int i=tot-1; i>=0; i--)P2[i]=1ll*P2[i + 1]*(i + 1)%mod;
}
int C(int n,int m) {
return 1ll*P1[n]*P2[m]%mod*P2[n-m]%mod;
}
void solve() {
int x,y;
cin>>x>>y;
if (y==0) {
cout<<"1\\
";
} else if (y>x) {
cout<<"0\\
";
} else if (x==y) {
cout<<P1[x-1]*P2[2]%mod<<'\\
';
} else {
int ans=0;
int p=1;
for(int i=1; i<=x-y; i + + ) {
if (y + i<i*2) continue;
int k=C(y + i,i*2)*p%mod;
p=p*(i*2 + 1)%mod;
k=k*P1[y-i]%mod;
k=k*C(y-1,i-1)%mod;
ans=(ans + C(x,x-y-i)*k)%mod;
}
cout<<ans<<'\\
';
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init(200000);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56231 people are learning the system