C 题解———2019.10.16

现在很痛苦，等过阵子回头看看，会发现其实那都不算事。

【题目描述】
定义一个排列 a 的价值为满足|a[i]-i|<=1 的 i 的数量。
给出三个正整数 n,m,p，求出长度为 n 且价值恰好为 m 的排列的个数对 p 取
模的结果。
【输入描述】
第一行两个正整数 T,p，T 为数据组数，p 为模数。
接下来 T 行，每行两个正整数 n,m。
【输出描述】
T 行，每行一个非负数，表示答案。
【输入样例】
5 1887415157
3 1
3 2
3 3
50 10
1500 200
【输出样例】
1
2
3
621655247
825984474
【数据范围】
10%的数据：n<=10
30%的数据：n<=15
50%的数据：n<=200
另有 10%的数据：m=1
另有 10%的数据：m=n-1
100%的数据：1<=T,n,m<=2000，2<=p<=10^12

---

 

题意：
定义一个排列 a 的价值为满足|a[i]-i|<=1 的 i 的数量。
给出三个正整数 n,m,p，求出长度为 n 且价值恰好为 m 的排列的个数对 p 取模的结果。
T组询问,p事先给出。

题解：
因为n,m <= 2000,而且p是事先给出的,所以我们可以一次性预处理出n,m <= 2000的答案。

考虑一个长度为i的排列如何变成长度为i+1的排列。
一种情况是我在它末尾加入了一个数i+1,另一种情况是我用i+1替换掉了原来排列中的一个数，然后把被换掉的数放到排列的末尾。
那么,这个排列权值的变化就是：
第一种情况：在它末尾加入了一个数i+1，权值+1。
第二种情况：用i+1替换掉一个数，权值 += 加的贡献 - 换掉的数的贡献。

在DP当中，我们只需要考虑替换掉的数是否是i,以及i是否在位置i/i-1即可。总共有5种本质不同的状态，分类讨论转移即可。
复杂度O(nm)。

---

 

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

typedef long long LL;

const int N=2005;

int q,n,m,u,v;
LL p,ans,f[N][N][5],x;

int rd(){
    int re=0,f=1;char c=getchar();
    while ((c<‘0‘)||(c>‘9‘)) {if (c==‘-‘) f=-f;c=getchar();}
    while ((c>=‘0‘)&&(c<=‘9‘)) {re=re*10+c-‘0‘;c=getchar();}
    return re*f;
}

int main(){
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    cin>>q>>p;
    memset(f,0,sizeof(f));
    f[1][1][0]=1ll;
    f[2][2][0]=1ll;f[2][2][1]=1ll;
    
    n=2000;
    for (int i=2;i<n;++i)
        for (int j=0;j<=n;++j){
            for (int k=0;k<=4;++k){
                x=f[i+1][j+1][0]+f[i][j][k];
                x=(x<p)?x:(x-p);
                f[i+1][j+1][0]=x;
                u=j+((k%2)==0);
                v=1+(k!=0);
                x=f[i+1][u][v]+f[i][j][k];
                x=(x<p)?x:(x-p);
                f[i+1][u][v]=x;
            }
            
            if (f[i][j][0]>0ll){
                f[i+1][j-1][4]=(f[i+1][j-1][4]+f[i][j][0]*(LL)(j-1))%p;
                f[i+1][j][4]=(f[i+1][j][4]+f[i][j][0]*(LL)(i-j))%p;
            }
            if (f[i][j][1]>0ll){
                x=f[i+1][j][3]+f[i][j][1];
                x=(x<p)?x:(x-p);
                f[i+1][j][3]=x;
                f[i+1][j-1][4]=(f[i+1][j-1][4]+f[i][j][1]*(LL)(j-2))%p;
                f[i+1][j][4]=(f[i+1][j][4]+f[i][j][1]*(LL)(i-j))%p;
            }
            if (f[i][j][2]>0ll){
                x=f[i+1][j][3]+f[i][j][2];
                x=(x<p)?x:(x-p);
                f[i+1][j][3]=x;
                f[i+1][j-1][4]=(f[i+1][j-1][4]+f[i][j][2]*(LL)(j-1))%p;
                f[i+1][j][4]=(f[i+1][j][4]+f[i][j][2]*(LL)(i-j-1))%p;                
            }
            if (f[i][j][3]>0ll){
                x=f[i+1][j+1][3]+f[i][j][3];
                x=(x<p)?x:(x-p);
                f[i+1][j+1][3]=x;
                f[i+1][j-1][4]=(f[i+1][j-1][4]+f[i][j][3]*(LL)(j-1))%p;
                f[i+1][j][4]=(f[i+1][j][4]+f[i][j][3]*(LL)(i-j-1))%p;    
            }
            if (f[i][j][4]>0ll){
                x=f[i+1][j+1][3]+f[i][j][4];
                x=(x<p)?x:(x-p);
                f[i+1][j+1][3]=x;        
                if (j>0) f[i+1][j-1][4]=(f[i+1][j-1][4]+f[i][j][4]*(LL)(j))%p;
                f[i+1][j][4]=(f[i+1][j][4]+f[i][j][4]*(LL)(i-j-2))%p;    
            }
        }
    
    for (;q>0;--q){
        cin>>n>>m;
        ans=(f[n][m][0]+f[n][m][1]+f[n][m][2]+f[n][m][3]+f[n][m][4])%p;
        cout<<ans<<‘\n‘;
    }
    return 0;
}

View Code