QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112889#5749. Directed Vertex CactiLWLAymhWA 4ms3148kbC++141.7kb2023-06-15 08:32:102023-06-15 08:32:11

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-15 08:32:11]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3148kb
  • [2023-06-15 08:32:10]
  • 提交

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'