QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91274 | #6137. Sub-cycle Graph | s8194272 | WA | 136ms | 5728kb | C++14 | 2.0kb | 2023-03-28 09:44:09 | 2023-03-28 09:44:12 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<random>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#define int long long
#define fi first
#define se second
#define max Max
#define min Min
#define abs Abs
#define lc (x<<1)
#define rc (x<<1|1)
#define mid ((l+r)>>1)
#define pb(x) push_back(x)
#define lowbit(x) ((x)&(-(x)))
#define fan(x) ((((x)-1)^1)+1)
#define mp(x,y) make_pair(x,y)
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
#define SZ(x) ((int)(x.size()))
#define INF 0x3f3f3f3f
using namespace std;
inline int read()
{
int ans=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){ans=(ans<<1)+(ans<<3)+c-'0';c=getchar();}
return ans*f;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x/10) write(x/10);
putchar((char)(x%10)+'0');
}
template<typename T>inline T Abs(T a){return a>0?a:-a;};
template<typename T,typename TT>inline T Min(T a,TT b){return a<b?a:b;}
template<typename T,typename TT> inline T Max(T a,TT b){return a<b?b:a;}
const int N=1e5+5,mod=1e9+7;
int t,n,m,jc[N],inv[N],pw[N];
inline int q_pow(int a,int b)
{
int c=1;
while(b)
{
if(b&1) c=a*c%mod;
a=a*a%mod;b>>=1;
}
return c;
}
inline void init(int x)
{
jc[0]=1;pw[0]=1;
for(int i=1;i<=x;++i)
{
jc[i]=jc[i-1]*i%mod;
pw[i]=pw[i-1]*(mod+1)/2%mod;
}
inv[x]=q_pow(jc[x],mod-2);
for(int i=x-1;i>=0;--i)
inv[i]=inv[i+1]*(i+1)%mod;
}
inline int C(int n,int m)
{
return n<m?0:jc[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main()
{
init(100000);
t=read();
while(t--)
{
n=read();m=read();
if(m>n) write(0);
else if(m==n) write(jc[n-1]);
else
{
int ans=0;
for(int i=0;i<=n-m;++i)
ans=(ans+C(n,i)*C(m-1,n-m-i-1)%mod*jc[n-i]%mod*inv[n-m-i]%mod*pw[n-m-i])%mod;
write(ans);
}
puts("");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5728kb
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: 136ms
memory: 5724kb
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:
0 3 3 2 0 6 15 12 6 0 10 45 90 60 24 0 15 105 375 630 360 120 0 21 210 1155 3465 5040 2520 720 0 28 378 2940 13545 35280 45360 20160 5040 0 36 630 6552 42525 170100 393120 453600 181440 40320 0 45 990 13230 114345 643545 2286900 4762800 4989600 1814400 362880 0 55 1485 24750 273735 2047815 10239075 ...
result:
wrong answer 1st numbers differ - expected: '1', found: '0'