QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#474521#2568. MountainsXiaoZi_qwqAC ✓1ms10036kbC++141.9kb2024-07-12 19:41:162024-07-12 19:41:16

Judging History

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

  • [2024-07-12 19:41:16]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:10036kb
  • [2024-07-12 19:41:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int read(){
  register int x=0;
  char c=getchar();
  while(c<'0' || '9'<c) c=getchar();
  while('0'<=c && c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
  return x;
}
const int N=110,Mmax=1000100;
int inv[Mmax<<1],fac[Mmax<<1],inv_fac[Mmax<<1],tot=1;
const int mod=1000000007;
int T,n,m,M[N][N],a[N],b[N],cnt;
inline int qpow(int base,int pow){
  int ans=1;
  while(pow){
    if(pow&1)
      ans=1ll*ans*base%mod;
    base=1ll*base*base%mod;
    pow>>=1;
  }
  return ans;
}
inline int C(int a,int b){return 1ll*fac[a]*inv_fac[a-b]%mod*inv_fac[b]%mod;}
int det(){
  int res=1;
  bool flag=false;//正负性 
  for(int i=1;i<=cnt;i++){
    int x=i;
    while(x<=cnt && !M[x][i]) x++; 
    if(x>cnt) return 0;
    if(x!=i){
      for(int j=i;j<=cnt;j++)
        swap(M[x][j],M[i][j]);
      flag^=1;
    }
    res=1ll*res*(M[i][i]+mod)%mod;
    int t=qpow(M[i][i],mod-2);
    for(int k=i+1;k<=cnt;k++){
      int t0=1ll*M[k][i]*t%mod;
      for(int j=i;j<=cnt;j++)
        M[k][j]=(M[k][j]-1ll*M[i][j]*t0)%mod;
    }
  }
  return flag?mod-res:res;
}
void slove(){
  scanf("%d%d%d",&n,&m,&cnt);n++,m++;
  while(tot<2*(m+n)){//计算组合数 的预处理 
    //原理 C(n,m)=n!/(n-m)!/m!
    //fac[i]=i!%mod inv_fac[i]=i!%mod的逆元
    //C(n,m)=fac[n]*inv_fac[n-m]*inv_fac[m]
    tot++;
    fac[tot]=1ll*fac[tot-1]*tot%mod;
    inv[tot]=1ll*(mod-mod/tot)*inv[mod%tot]%mod;
    inv_fac[tot]=1ll*inv_fac[tot-1]*inv[tot]%mod;
  }
  //for(int i=1;i<=m;i++) scanf("%d %d",a+i,b+i);
  for(int i=1;i<=cnt;i++)//(i,m+i-1) 起点 
    for(int j=1;j<=cnt;j++)//(n+j-1,j) 终点 
      M[i][j]=(i<=n+j-1 && m+i-1>=j)?C(n+m-2,m+i-1-j):0;
  printf("%d\n",det());
}
int main()
{
	//freopen("test.in","r",stdin);
	//scanf("%d",&T);
	fac[0]=inv_fac[0]=1;
	fac[1]=inv_fac[1]=inv[1]=1;
  slove();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 7908kb

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 7908kb

input:

2 2 2

output:

20

result:

ok 1 number(s): "20"

Test #3:

score: 0
Accepted
time: 0ms
memory: 7968kb

input:

2 3 4

output:

490

result:

ok 1 number(s): "490"

Test #4:

score: 0
Accepted
time: 0ms
memory: 7860kb

input:

1 2 8

output:

45

result:

ok 1 number(s): "45"

Test #5:

score: 0
Accepted
time: 0ms
memory: 7900kb

input:

1 10 2

output:

66

result:

ok 1 number(s): "66"

Test #6:

score: 0
Accepted
time: 0ms
memory: 7972kb

input:

9 5 7

output:

371850968

result:

ok 1 number(s): "371850968"

Test #7:

score: 0
Accepted
time: 1ms
memory: 8052kb

input:

3 3 1

output:

20

result:

ok 1 number(s): "20"

Test #8:

score: 0
Accepted
time: 1ms
memory: 8052kb

input:

7 7 9

output:

166345303

result:

ok 1 number(s): "166345303"

Test #9:

score: 0
Accepted
time: 1ms
memory: 8056kb

input:

25 15 25

output:

850087558

result:

ok 1 number(s): "850087558"

Test #10:

score: 0
Accepted
time: 1ms
memory: 8004kb

input:

45 59 71

output:

659153227

result:

ok 1 number(s): "659153227"

Test #11:

score: 0
Accepted
time: 1ms
memory: 7980kb

input:

73 3 25

output:

683124269

result:

ok 1 number(s): "683124269"

Test #12:

score: 0
Accepted
time: 1ms
memory: 8008kb

input:

1 48 78

output:

446896916

result:

ok 1 number(s): "446896916"

Test #13:

score: 0
Accepted
time: 1ms
memory: 8056kb

input:

25 100 32

output:

966287506

result:

ok 1 number(s): "966287506"

Test #14:

score: 0
Accepted
time: 1ms
memory: 7872kb

input:

85 64 40

output:

125679545

result:

ok 1 number(s): "125679545"

Test #15:

score: 0
Accepted
time: 1ms
memory: 7928kb

input:

5 9 94

output:

620471576

result:

ok 1 number(s): "620471576"

Test #16:

score: 0
Accepted
time: 1ms
memory: 7996kb

input:

33 57 40

output:

637315057

result:

ok 1 number(s): "637315057"

Test #17:

score: 0
Accepted
time: 1ms
memory: 7952kb

input:

61 6 97

output:

362472796

result:

ok 1 number(s): "362472796"

Test #18:

score: 0
Accepted
time: 1ms
memory: 7912kb

input:

85 50 51

output:

192099209

result:

ok 1 number(s): "192099209"

Test #19:

score: 0
Accepted
time: 1ms
memory: 7924kb

input:

96 54 59

output:

714762612

result:

ok 1 number(s): "714762612"

Test #20:

score: 0
Accepted
time: 1ms
memory: 7992kb

input:

20 99 12

output:

772155662

result:

ok 1 number(s): "772155662"

Test #21:

score: 0
Accepted
time: 1ms
memory: 7880kb

input:

48 39 62

output:

670046604

result:

ok 1 number(s): "670046604"

Test #22:

score: 0
Accepted
time: 1ms
memory: 7892kb

input:

76 83 16

output:

976820079

result:

ok 1 number(s): "976820079"

Test #23:

score: 0
Accepted
time: 1ms
memory: 7924kb

input:

96 36 61

output:

20854557

result:

ok 1 number(s): "20854557"

Test #24:

score: 0
Accepted
time: 1ms
memory: 7888kb

input:

18 40 77

output:

261684871

result:

ok 1 number(s): "261684871"

Test #25:

score: 0
Accepted
time: 1ms
memory: 8056kb

input:

42 84 26

output:

458573307

result:

ok 1 number(s): "458573307"

Test #26:

score: 0
Accepted
time: 1ms
memory: 8004kb

input:

71 25 80

output:

875902815

result:

ok 1 number(s): "875902815"

Test #27:

score: 0
Accepted
time: 1ms
memory: 10036kb

input:

95 73 26

output:

922299967

result:

ok 1 number(s): "922299967"

Test #28:

score: 0
Accepted
time: 1ms
memory: 8004kb

input:

19 17 83

output:

494148696

result:

ok 1 number(s): "494148696"

Test #29:

score: 0
Accepted
time: 1ms
memory: 8028kb

input:

100 100 100

output:

192912055

result:

ok 1 number(s): "192912055"

Test #30:

score: 0
Accepted
time: 1ms
memory: 8004kb

input:

100 98 99

output:

412293529

result:

ok 1 number(s): "412293529"