QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #474026 | #2568. Mountains | xcyyyyy | WA | 1ms | 3956kb | C++14 | 1.1kb | 2024-07-12 15:36:34 | 2024-07-12 15:36:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define x first
#define y second
#define p 1000000007
#define ll long long
int n,m,k;
pair<int,int> s[N],t[N];
ll a[N][N],fac[N],inv[N],pinv[N];
inline ll C(int n,int m){return n<0||m<0||n<m?0:fac[n]*pinv[m]%p*pinv[n-m]%p;}
inline ll qpow(ll a,int b){ll ans=1;for(;b;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;return ans;}
inline ll det(int n){
ll ans=1;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++)if(a[j][i]){swap(a[j],a[i]);ans=-ans;break;}
for(int j=i+1;j<=n;j++){
ll t=a[j][i]*qpow(a[i][i],p-2)%p;
for(int k=i;k<=n;k++)a[j][k]=(a[j][k]-a[i][k]*t%p+p)%p;
}
}
for(int i=1;i<=n;i++)ans=ans*a[i][i]%p;
return (ans+p)%p;
}
int main(){
fac[0]=fac[1]=inv[0]=inv[1]=pinv[0]=pinv[1]=1;
for(int i=2;i<N;i++)fac[i]=fac[i-1]*i%p,inv[i]=inv[p%i]*(p-p/i)%p,pinv[i]=pinv[i-1]*inv[i]%p;
scanf("%d%d%d",&n,&m,&k);
s[1]={n,0};t[1]={0,m};
for(int i=2;i<=k;i++)
s[i]=s[i-1],++s[i].first,++s[i].second,
t[i]=t[i-1],++t[i].first,++t[i].second;
for(int i=1;i<=k;i++)for(int j=1;j<=k;j++)a[i][j]=C(s[i].x-t[j].x + t[j].y-s[i].y,t[j].y-s[i].y);
printf("%lld",det(k));
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3868kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
2 2 2
output:
20
result:
ok 1 number(s): "20"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
2 3 4
output:
490
result:
ok 1 number(s): "490"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
1 2 8
output:
45
result:
ok 1 number(s): "45"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
1 10 2
output:
66
result:
ok 1 number(s): "66"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
9 5 7
output:
371850968
result:
ok 1 number(s): "371850968"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
3 3 1
output:
20
result:
ok 1 number(s): "20"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
7 7 9
output:
166345303
result:
ok 1 number(s): "166345303"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
25 15 25
output:
850087558
result:
ok 1 number(s): "850087558"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
45 59 71
output:
659153227
result:
ok 1 number(s): "659153227"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
73 3 25
output:
683124269
result:
ok 1 number(s): "683124269"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3940kb
input:
1 48 78
output:
446896916
result:
ok 1 number(s): "446896916"
Test #13:
score: -100
Wrong Answer
time: 0ms
memory: 3912kb
input:
25 100 32
output:
0
result:
wrong answer 1st numbers differ - expected: '966287506', found: '0'