CF285E Positions in Permutations

What is different from others here is modulo addition and multiplication (I think this thing is very good, maybe a little faster?

Solution

First, it allows us to calculate the number of schemes, so we set an array \ (F(x) \) to represent the number of permutations whose perfect number is exactly \ (x \). From this familiar coincidence, we can set another array \ (G(x) \) to represent the number of permutations whose perfect number is at least \ (x \), so it is obvious that: \ (g (m) = \ sum \ limits can be obtained_ {I = m} ^ n \ binom IMF (I) \), a normal binomial inversion can get \ (F(m)=\sum\limits_{i=m}^n(-1)^{i-m}\binom imG(i) \), now consider how to find \ (G(x) \).

Because the perfection of each bit is only related to the front and back, we can set \ (f_{i,j,0/1,0/1} \) to indicate that the current bit is \ (i \), there are \ (j \) perfect numbers, \ (i \) yes / no and \ (i+1 \) yes / No.

Now consider the state transition equation:

Select bit \ (I \) as the perfect bit and put \ (i-1 \) in bit \ (I \), just make sure that \ (i-1 \) is not selected.

\[f_{i,j,0,0}+=f_{i-1,j-1,0,0},f_{i,j,1,0}+=f_{i-1,j-1,0,1} \]

Select bit \ (i \) as the perfect bit and put \ (i+1 \) in bit \ (i \), just make sure that \ (i+1 \) is not selected.

\[f_{i,j,0,1}+=f_{i-1,j-1,0,0}+f_{i-1,j-1,1,0},f_{i,j,1,1}+=f_{i-1,j-1,0,1}+f_{i-1,j-1,1,1} \]

Do not select bit \ (i \) as the perfect bit

\[f_{i,j,0,0}+=f_{i-1,j,0,0}+f_{i-1,j,1,0},f_{i,j,1,0}+=f_{i-1,j,0,1}+f_{i-1,j,1,1} \]

Initial state: \ (f_{1,0,0,0}=1,f_{1,1,0,1}=1 \)

Because the \ (n \) bit can only select \ (n-1 \) as the perfect number, it is necessary to transfer or subtract the part of \ (n+1 \). I chose to relocate.

Now you can get \ (g (m) = (f {n, m, 0,0} + F {n, m, 1,0}) \ times (n-m)! \), Where \ ((n-m)! \) It is the full arrangement of the remaining \ (n-m \) positions.

Finally, inversion is enough.

code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;
const int N=2050,mod=1e9+7;
int n,m;
ll f[N][N][2][2],G[N],fac[N],inv[N];

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

ll mul(ll a,ll b){return a*b%mod;}
ll add(ll a,ll b){return a+b>=mod?a+b-mod:a+b;}

inline void init(){
    fac[0]=inv[0]=inv[1]=1;
    for(int i=2;i<=n;i++)
        inv[i]=mul(inv[mod%i],mod-mod/i);
    for(int i=1;i<=n;i++){
        fac[i]=mul(fac[i-1],i);
        inv[i]=mul(inv[i],inv[i-1]);
    }
}

ll C(int n,int m){
    if(n<m) return 0;
    return mul(fac[n],mul(inv[n-m],inv[m]));
}

int main(){
    n=read();m=read();
    init();
    f[1][0][0][0]=f[1][1][0][1]=1;
    for(int i=2;i<=n;i++){
        f[i][0][0][0]=1;
        for(int j=1;j<=i;j++){
            f[i][j][0][0]=add(f[i-1][j-1][0][0],add(f[i-1][j][0][0],f[i-1][j][1][0]));
            f[i][j][0][1]=add(f[i-1][j-1][0][0],f[i-1][j-1][1][0]);
            f[i][j][1][0]=add(f[i-1][j-1][0][1],add(f[i-1][j][1][1],f[i-1][j][0][1]));
            f[i][j][1][1]=add(f[i-1][j-1][0][1],f[i-1][j-1][1][1]);
        }
    }
    f[n][0][0][0]=1;
    for(int i=1;i<=n;i++){
        f[n][i][0][0]=add(f[n-1][i-1][0][0],add(f[n-1][i][0][0],f[n-1][i][1][0]));
        f[n][i][1][0]=add(f[n-1][i-1][0][1],add(f[n-1][i][0][1],f[n-1][i][1][1]));
    }
    //Above is the retransfer n
    for(int i=0;i<=n;i++)
        G[i]=mul(add(f[n][i][0][0],f[n][i][1][0]),fac[n-i]);
    ll ans=0;
    for(int i=m;i<=n;i++){
        ll res=mul(C(i,m),G[i]);
        ans=add(ans,(i-m)&1?mod-res:res);
    }
    printf("%lld\n",ans);
    return 0;
}

Tags: Dynamic Programming Math

Posted by winmastergames on Thu, 12 May 2022 11:41:57 +0300