hdu 5894 점 위치 (조합 수학, 심양 인터넷 경기)

제목:http://acm.hdu.edu.cn/showproblem.php?pid=5894 제목:
현재 m 명의 수험생 은 n 개의 좌석 이 있 는 원탁 에 앉 아야 한다.너 는 임의의 두 수험생 사이 에 적어도 k 개의 위 치 를 두 도록 위 치 를 안배 해 야 한다.책상 에 번호 가 있 고 수험생 a 와 b 가 위 치 를 교환 하 는 것 을 하나의 방안 으로 보고 몇 가지 방안 이 있 는 지 물 었 다. mod 1e9 + 7.(0 < m < n < 1e6, 0 < k < 1000)
분석:
이 문 제 는 동료 가 지나 간 것 을 보충 합 니 다 ~ 먼저 첫 번 째 사람의 위 치 를 확인 하고 첫 번 째 사람 은 n 개의 의자 중에서 하 나 를 선택 한 다음 n - 1 개의 의 자 를 남 길 수 있 습 니 다.사람의 간격 이 적어도 k 개의 의자 가 있 기 때문에 요구 에 부합 되 는 간격 이 있 는 의자 에서 k * m 개 를 뽑 고 나머지 m - 1 명 은 남 은 의자 에서 마음대로 고 를 수 있다.모든 사람 이 k 개의 좌석 과 함께 묶 여 있다 고 상상 할 수 있 습 니 다. 이 사람 이 자리 가 생기 면 그 뒤에 자동 으로 k 개의 좌석 을 추가 합 니 다.그러면 첫 번 째 사람 이 n 개의 좌석 중에서 하 나 를 선택 하고 k * m 개 를 빼 면 n - 1 - k * m 의 좌석 이 남 습 니 다. 그 중에서 m - 1 개 를 다른 사람 에 게 주 는 좌석 으로 선택 하고 총 수 는 sum = n * C (n - 1 - k * m, m - 1) 입 니 다. 여기 있 는 사람 은 차이 가 없 기 때 문 입 니 다.예 를 들 어 세 사람 이 앉 은 위치 가 (2, 4, 7) 이 라 고 가정 하면 (4, 2, 7), (7, 2, 4) 는 반복 적 으로 계산 되 고 모든 sum / m 이다.
코드:

#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll qmod(ll x,int n) {
    ll ans=1;
    for(; n; n>>=1) {
        if(n&1)ans=ans*x%mod;
        x=x*x%mod;
    }
    return ans;
}
ll C(int n,int m) {
    if(m>n)return 0;
    ll ans=1;
    for(int i=1; i<=m; i++) {
        ans=ans*((n+i-m)*qmod(i,mod-2)%mod)%mod;
    }
    return ans;
}
int main() {
    // freopen("f.txt","r",stdin);
    int T;
    scanf("%d",&T);
    ll n,m,k;
    while(T--) {
        scanf("%lld%lld%lld",&n,&m,&k);
        if(m==1)printf("%lld
",n);
        else
            printf("%lld
",(C(n-k*m-1,m-1)*n%mod)*qmod(m,mod-2)%mod);
    }
    return 0;
}