Submission #2927039

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
ll dp[1005][2],n,k,p[1005],o[1005];
ll pw(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1)res=res*x%M;
        x=x*x%M;
        y>>=1;
    }
    return res;
}
ll cm(ll x,ll y){
    return p[x]*o[y]%M*o[x-y]%M;
}
int main(void){
    cin>>n>>k;
    p[0]=1;
    o[0]=1;
    for(ll i=1;i<=n;i++){
        p[i]=p[i-1]*i%M;
        o[i]=pw(p[i],M-2);
    }
    dp[0][0]=1;
    for(ll i=0;i<n;i++){
        for(ll j=2;i+j<=n;j++){
            if(j==k)dp[i+j][1]=(dp[i+j][1]+dp[i][0]*cm(n-i-1,j-1)%M*p[j-1]%M)%M;
            else dp[i+j][0]=(dp[i+j][0]+dp[i][0]*cm(n-i-1,j-1)%M*p[j-1]%M)%M;
            dp[i+j][1]=(dp[i+j][1]+dp[i][1]*cm(n-i-1,j-1)%M*p[j-1]%M)%M;
        }
    }
    printf("%lld\n",dp[n][1]);
}

Submission Info

Judge Result