QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#131303 | #6137. Sub-cycle Graph | stefanbalaz2 | WA | 266ms | 4836kb | C++14 | 1.8kb | 2023-07-26 21:23:13 | 2023-07-26 21:23:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
typedef pair<int,int> pii;
const int mod=1e9+7;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}
const int maxn=1e5+10;
int fact[maxn],inv[maxn],prek2[maxn];
int c(int n,int k){
if(n<0 || k<0 || n<k)return 0;
return mul(fact[n],mul(inv[k],inv[n-k]));
}
int pw2(int n){
if(n<0)return 0;
if(n==0)return 1;
if(prek2[n]!=-1)return prek2[n];
prek2[n]=mul(pw2(n-1),2);
return prek2[n];
}
int main() {
///freopen("test.txt","r",stdin);
inv[0]=fact[0]=1;
for(int i=1;i<maxn;i++){
fact[i]=mul(fact[i-1],i);
inv[i]=invv(fact[i]);
}
memset(prek2,-1,sizeof(prek2));
int t;
scanf("%d",&t);
while(t--){
int n;
ll m;
scanf("%d %lld",&n,&m);
ll k=n-m;
if(k<0){
printf("0\n");
continue;
}
if(k==0){
printf("1\n");
continue;
}
int rez=0;
for(int i=0;i<=n-1;i++){
int oc=n-1-i;
int pom=1;
if(oc%2)pom=mod-1;
rez=add( rez, mul( c(i,k-1) , mul(c(k,oc),mul(pom,pw2(k-oc)) ) ) );
}
rez=mul(rez,fact[n]);
rez=mul(rez,inv[k]);
rez=mul(rez,invv(step(2,k)));
printf("%d\n",rez);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 12ms
memory: 4836kb
input:
3 4 2 4 3 5 3
output:
15 12 90
result:
ok 3 number(s): "15 12 90"
Test #2:
score: -100
Wrong Answer
time: 266ms
memory: 4784kb
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 1 1 6 15 12 1 1 10 45 90 60 1 1 15 105 375 630 360 1 1 21 210 1155 3465 5040 2520 1 1 28 378 2940 13545 35280 45360 20160 1 1 36 630 6552 42525 170100 393120 453600 181440 1 1 45 990 13230 114345 643545 2286900 4762800 4989600 1814400 1 1 55 1485 24750 273735 2047815 10239075 32848200 62370000...
result:
wrong answer 9th numbers differ - expected: '3', found: '1'