QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#112889 | #5749. Directed Vertex Cacti | LWLAymh | WA | 4ms | 3148kb | C++14 | 1.7kb | 2023-06-15 08:32:10 | 2023-06-15 08:32:11 |
Judging History
answer
#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
struct FastMod
{
using ull=unsigned long long;
using L=__int128;
ull b,m;
FastMod(ull b):b(b),m(ull((L(1)<<64)/b)){}
ull reduce(ull a)// return a mod b
{
ull q=(ull)((L(m)*a)>>64),r=a-q*b;
return r>=b?r-b:r;
}
}F(998244353);
inline ll mpow(ll x,ll k){
ll ans=1;
for(;k;k=k>>1,x=F.reduce(x*x)){
if(k&1)ans=F.reduce(ans*x);
}
return ans;
}
namespace FastIO
{
const int SIZE=(1<<21)+1;
char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=obuf;
char* flush(){fwrite(obuf,1,oT-oS,stdout);return oT=obuf;}
struct Flusher{~Flusher(){flush();}}flusher;
inline char gc(){return iS==iT && (iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT)?EOF:*iS++;}
inline void pc(char c){if(oT==oS+SIZE) flush();*oT++=c;}
template<typename T=int>
T read(){T x=0;char ch=gc();for(;ch<'0' || ch>'9';ch=gc());for(;ch>='0' && ch<='9';ch=gc()) x=x*10+(ch-'0');return x;}
template<typename T>
void write(T x){if(x>=10) write(x/10);pc(x%10+'0');}
}
using FastIO::gc;
using FastIO::pc;
using FastIO::read;
using FastIO::write;
int n,m;
ll mod;
inline ll get_fac(int n){
ll ans=1;
for(int i=1;i<=n;++i)ans=F.reduce(ans*i);
return ans;
}
inline ll get_C(ll n,int m){
n%=mod;
ll ans=1;
for(int i=0;i<m;++i){
ans=F.reduce(ans*(n-i));
}
return F.reduce(mpow(get_fac(m),mod-2)*ans);
}
int main(){
// freopen("graph.in","r",stdin);
// freopen("graph.out","w",stdout);
scanf("%d%d",&n,&m);mod=1e9+7;
F=FastMod(mod);
printf("%lld\n",F.reduce(get_fac(n)*get_C((1ll*n*(n-1))>>1,m))%mod);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3148kb
input:
3 1
output:
18
result:
ok 1 number(s): "18"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3040kb
input:
4 4
output:
360
result:
ok 1 number(s): "360"
Test #3:
score: -100
Wrong Answer
time: 4ms
memory: 3040kb
input:
39847 348708
output:
448520477
result:
wrong answer 1st numbers differ - expected: '983575456', found: '448520477'