Codeforces Global Round 24 D()

D. Doremy’s Pegging Game

题目链接
挺难的一道计数
计数问题最重要的是考虑如果划分集合 然后不重不漏地计算出来
我们考虑枚举每一个序列的结束点
就是有n个 然后这n个显然是等价的 所以我们最后n即可
然后我们可以发现我们结束状态一定是“一边”点 就是最远的点距离不超过n/2
这样我们就可以枚举“边”的起始 然后O（1）计算即可
我们边中间的可以在可以不在
设边除了起始两个点还有x个点
然后可以预处理边内点选i=0，1，2，3，….x个要删掉时的也就是Cxi再一共有多少点删掉的全排列
我们预处理出这个sum[x]
最后再枚举边的时候判断一下合法性
再最后判断一下n是偶数是 可以有一种特殊的对着的两个点的特殊情况即可

int a[N],b[N],p;
int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1)res=(res*a)%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
}
int C(int x,int y){
    if(x<0||y<0||x<y)return 0;
    return a[x]*b[y]%p*b[x-y]%p;
}
vector<int>A(N);
void init(){
    a[0]=b[0]=1;
    for(int i=1;i<=1e5;i++){
        a[i]=(a[i-1]*i)%p;
        b[i]=b[i-1]*qmi(i,p-2,p)%p;
    }
}
void solve(){
    int n;cin>>n>>p;
    init();
    A[0]=1;
    for(int i=1;i<=n;i++)A[i]=A[i-1]*i%p;
    vector<int>sum(n+10);
    for(int x=0;x<=n-3;x++){
        for(int j=0;j<=x;j++){
            (sum[x]+=C(x,j)*A[n-x-3+j]%p)%=p;
        }
    }
    int ans=0;
    for(int i=2;i<=n/2+1;i++){
        for(int j=i+1;j<=n;j++){
            int x=j-i;
            if(x<up(n,2)&&j>up(n,2)){
                (ans+=sum[x-1])%=p;
            }
        }
    }
    if(n%2==0){
        (ans+=A[n-2])%=p;
    }
    cout<<ans*n%p<<endl;
}
————————

D. Doremy’s Pegging Game

题目链接
挺难的一道计数
计数问题最重要的是考虑如果划分集合 然后不重不漏地计算出来
我们考虑枚举每一个序列的结束点
就是有n个 然后这n个显然是等价的 所以我们最后n即可
然后我们可以发现我们结束状态一定是“一边”点 就是最远的点距离不超过n/2
这样我们就可以枚举“边”的起始 然后O（1）计算即可
我们边中间的可以在可以不在
设边除了起始两个点还有x个点
然后可以预处理边内点选i=0，1，2，3，….x个要删掉时的也就是Cxi再一共有多少点删掉的全排列
我们预处理出这个sum[x]
最后再枚举边的时候判断一下合法性
再最后判断一下n是偶数是 可以有一种特殊的对着的两个点的特殊情况即可

int a[N],b[N],p;
int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1)res=(res*a)%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
}
int C(int x,int y){
    if(x<0||y<0||x<y)return 0;
    return a[x]*b[y]%p*b[x-y]%p;
}
vector<int>A(N);
void init(){
    a[0]=b[0]=1;
    for(int i=1;i<=1e5;i++){
        a[i]=(a[i-1]*i)%p;
        b[i]=b[i-1]*qmi(i,p-2,p)%p;
    }
}
void solve(){
    int n;cin>>n>>p;
    init();
    A[0]=1;
    for(int i=1;i<=n;i++)A[i]=A[i-1]*i%p;
    vector<int>sum(n+10);
    for(int x=0;x<=n-3;x++){
        for(int j=0;j<=x;j++){
            (sum[x]+=C(x,j)*A[n-x-3+j]%p)%=p;
        }
    }
    int ans=0;
    for(int i=2;i<=n/2+1;i++){
        for(int j=i+1;j<=n;j++){
            int x=j-i;
            if(x<up(n,2)&&j>up(n,2)){
                (ans+=sum[x-1])%=p;
            }
        }
    }
    if(n%2==0){
        (ans+=A[n-2])%=p;
    }
    cout<<ans*n%p<<endl;
}