BZOJ 4934: [Ceoi2016]kangaroo

强lu这道题，真的蓝瘦 QAQ 幸好有人带带我 2333

题解链接：http://pan.baidu.com/s/1nvIFO5V 密码：6igy

代码1：

#include<cstdio>
using namespace std;
const int N=2002,P=1e9+7;
char B[1<<14],*S=B,*T=B;
#define gc (S==T&&(T=(S=B)+fread(B,1,1<<14,stdin),S==T)?-1:*S++)
inline int read(){
    int x=0,f=1; char ch=gc;
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=gc;}
    while(ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=gc;}
    return x*f;
}
inline void up(int&x,int y){x=x+y<P?x+y:x+y-P;}
int i,j,f[N][N],u;
int main(){
    int n=read(),s=read(),t=read(); f[0][0]=1;
    for(i=1;i<=n;++i) for(j=0;j<i;++j) if(u=f[i-1][j])
        if(i!=s && i!=t){
            up(f[i][j+1],u);
            if(j) up(f[i][j-1],1ll*u*j%P*(j-1+(i>s)+(i>t))%P);
        }
        else{
            up(f[i][j],u);
            if(j) up(f[i][j-1],1ll*u*j%P);
        }
    printf("%d\n",f[n-1][0]);
    return 0;
}

代码二：（from DraZxlNDdt）

#include<bits/stdc++.h>
using namespace std;

const int P = 1e9 + 7, N = 2005;

int n, s, t, f[N][N];

void up (int &x, int y) { x += y; if (x >= P) x -= P; }

int Solve (int s, int t) {
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int i = 0, k; i < n - 1; ++i) {
        for (int j = 0; j <= i; ++j) if (f[i][j]) {
            if (i + 1 == s) {
                up(f[i + 1][j + 1], f[i][j]);
            } else if (i + 1 == t) {
                if (n & 1) up(f[i + 1][j + 1], f[i][j]); // n为奇， 最后一对数递减 
                else up(f[i + 1][j], 1ll * f[i][j] * (j - (s <= i)) % P); // 递增 
            } else {
                k = (s <= i) + (t <= i);
                up(f[i + 1][j + 1], f[i][j]);
                up(f[i + 1][j - 1], 1ll * (j - k) * (j - 1) % P * f[i][j] % P);
            }
        }
    }
    return f[n - 1][2 - (s == n || t == n)];
}

int main () {
    scanf("%d%d%d", &n, &s, &t);
    if (n == 1) return puts("1"), 0;
    if (s == t) return puts("0"), 0;
    int ans = Solve(s, t);
    ans = (ans + Solve(n - s + 1, n - t + 1)) % P;
    if (ans < 0) ans += P;
    printf("%d\n", ans);
    return 0;
}