[AtCoder] ARC 077 D:11
題目連結:http://arc077.contest.atcoder.jp/tasks/arc077_b
我賽中的時候蠢蠢的,一直想說要$\binom{n+1}{k}-\sum^{n+1}_{i=1}{\binom{p-1}{i} \times \binom{n+1-q}{n+1-i}}$,後來才發現其實那就等價於$\binom{n+1}{k}-\binom{n-q+p}{k-1}$,其中$p,q$為重複的那兩個數的位置。
我賽中的時候蠢蠢的,一直想說要$\binom{n+1}{k}-\sum^{n+1}_{i=1}{\binom{p-1}{i} \times \binom{n+1-q}{n+1-i}}$,後來才發現其實那就等價於$\binom{n+1}{k}-\binom{n-q+p}{k-1}$,其中$p,q$為重複的那兩個數的位置。
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 100000 + 5;
const int mod = 1000000007;
int arr[N], pos[N];
lld moni[N], cmb[2][N];
lld qPow(lld,lld);
lld C(int,int);
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n, p, q;cin>>n;
for(int i=1;i<=n+5;i++) moni[i]=qPow(i, mod-2);
for(int i=0;i<=n;i++) cin>>arr[i];
fill(pos, pos+1+n, -1);
for(int i=0;i<=n;i++){
if(pos[arr[i]]==-1) pos[arr[i]]=i;
else{
p=pos[arr[i]];
q=i;
break;
}
}
cmb[0][0]=1;
cmb[1][0]=1;
for(int i=1;i<=n+1;i++){
if(n+1-i+1 >= 1)
cmb[0][i]=(((cmb[0][i-1]*(lld)(n+1-i+1))%mod)*moni[i])%mod;
if(n-q+p-i+1 >= 1)
cmb[1][i]=(((cmb[1][i-1]*(lld)(n-q+p-i+1))%mod)*moni[i])%mod;
}
for(int i=1;i<=n+1;i++)
cout<<(cmb[0][i] - cmb[1][i-1] + mod)%mod<<'\n';
return 0;
}
lld qPow(lld a, lld b){
lld r=1;
while(b){
if(b&1) r=(r*a)%mod;
b>>=1;
a=(a*a)%mod;
}
return r%mod;
}
留言
張貼留言