QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94431 | #6137. Sub-cycle Graph | xuzhihaodedie | TL | 29ms | 4868kb | C++14 | 1.4kb | 2023-04-05 22:35:37 | 2023-04-05 22:35:40 |
Judging History
answer
// Problem: E. Living Sequence
// Contest: Codeforces - Codeforces Round 863 (Div. 3)
// URL: https://codeforces.com/contest/1811/problem/E
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=1e5+10;
int fact[N],infact[N];
int qpow(int a,int b) {
if(b==0) return 1;
if(b&1) return a*qpow(a,b-1)%mod;
else {
int mul=qpow(a,b/2)%mod;
return mul*mul%mod;
}
}
void init() {
fact[0]=infact[0]=1;
for(int i=1;i<N;i++) {
fact[i]=fact[i-1]*i%mod;
infact[i]=qpow(fact[i],mod-2)%mod;
}
}
int c(int n,int m) {
if(n<m) return 0;
if(n<0||m<0) return 0;
return fact[n]*infact[n-m]%mod*infact[m]%mod;
}
void solve() {
int n,m;
cin>>n>>m;
if(m>n) {
cout<<0<<endl;
return ;
}
if(m==0) {
cout<<1<<endl;
return ;
}
if(m==n) {
if(n<=2) {
cout<<0<<endl;
} else {
cout<<fact[n-1]*qpow(2,mod-2)%mod;
}
return ;
}
int ans=0;
for(int t=0;t<=n-m;t++) {
//if(n-m-t<0) continue;
int res=c(n,t)*c(n-t,2*(n-m-t))%mod*c(m-1,n-m-t-1)%mod;
int ret=fact[2*(n-m-t)]%mod*infact[n-m-t]%mod*qpow(qpow(2,n-m-t),mod-2)%mod;
ans=(ans+ret*res%mod*fact[max(0ll,2*m+t-n)]%mod)%mod;
}
cout<<ans<<endl;
}
signed main() {
int T=1;
init();
cin>>T;
while(T--) {
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 29ms
memory: 4868kb
input:
3 4 2 4 3 5 3
output:
15 12 90
result:
ok 3 number(s): "15 12 90"
Test #2:
score: -100
Time Limit Exceeded
input:
17446 3 0 3 1 3 2 3 3 4 0 4 1 4 2 4 3 4 4 5 0 5 1 5 2 5 3 5 4 5 5 6 0 6 1 6 2 6 3 6 4 6 5 6 6 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 8 0 8 1 8 2 8 3 8 4 8 5 8 6 8 7 8 8 9 0 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 10 0 10 1 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 11 0 11 1 11 2 11 3 11 4 11 5 11 6 11 7 11...
output:
1 3 3 11 6 15 12 31 10 45 90 60 121 15 105 375 630 360 601 21 210 1155 3465 5040 2520 3601 28 378 2940 13545 35280 45360 20160 25201 36 630 6552 42525 170100 393120 453600 181440 201601 45 990 13230 114345 643545 2286900 4762800 4989600 1814400 1814401 55 1485 24750 273735 2047815 10239075 32848200 ...