QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91057 | #6137. Sub-cycle Graph | yyyyxh | RE | 3ms | 2200kb | C++17 | 1.2kb | 2023-03-26 22:18:05 | 2023-03-26 22:18:06 |
Judging History
answer
#include <cstdio>
using namespace std;
template<typename T>
T read(){
char c=getchar();T x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
typedef long long ll;
const int P=1000000007;
int qp(int a,int b=P-2){
int res=1;
while(b){
if(b&1) res=(ll)res*a%P;
a=(ll)a*a%P;b>>=1;
}
return res;
}
int fac[100003],fiv[100003];
int comb(int a,int b){
return (ll)fac[a]*fiv[b]%P*fiv[a-b]%P;
}
void inc(int &x,int v){if((x+=v)>=P) x-=P;}
void dec(int &x,int v){if((x-=v)<0) x+=P;}
int main(){
int tc=read<int>();
fac[0]=1;
for(int i=1;i<=100000;++i) fac[i]=(ll)fac[i-1]*i%P;
fiv[100000]=qp(fac[100000]);
for(int i=100000;i;--i) fiv[i-1]=(ll)fiv[i]*i%P;
while(tc--){
int n=read<int>();
ll m=read<ll>();
if(m>n){puts("0");continue;}
if(m==n){printf("%d\n",fac[n-1]);continue;}
m=n-m;
int pw=1,res=0;
for(int i=0;i<=m;++i){
if((m^i)&1) dec(res,(ll)comb(m,i)*pw%P*comb(n-m+i-1,m-1)%P);
else inc(res,(ll)comb(m,i)*pw%P*comb(n-m+i-1,m-1)%P);
inc(pw,pw);
}
res=(ll)res*fiv[m]%P*fac[n]%P*qp((P+1)>>1,m)%P;
printf("%d\n",res);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 2200kb
input:
3 4 2 4 3 5 3
output:
15 12 90
result:
ok 3 number(s): "15 12 90"
Test #2:
score: -100
Runtime Error
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 2 1 6 15 12 6 1 10 45 90 60 24 1 15 105 375 630 360 120 1 21 210 1155 3465 5040 2520 720 293849209 28 378 2940 13545 35280 45360 20160 5040 852231769 334709860 630 6552 42525 170100 393120 453600 181440 40320 337404719 203419777 990 13230 114345 643545 2286900 4762800 4989600 1814400 362880 24...