0 like 0 dislike
896 views
| 896 views

0 like 0 dislike

IMAGES OF QUES

by Expert (46,090 points)
0 like 0 dislike

Solution in O(n^2) time, for each restricted position we have a[i]>a[i+1]<a[i+2] or a[i]<a[i+1]>a[i+2]. Ofcourse if we have the same type of restriction for two consecutive place then there is not even a single good permutation. Otherwise the n length sequence breaks up to smaller blocks, where in each block we see that: a[k]<a[k+1]>a[k+2]<a[k+3]>a[k+4]< etc. or a[k]>a[k+1]<a[k+2]>a[k+3]<a[k+4]> etc. but notice that it isn't interesting that we see which sequence we have the same number of possibilities due to the x->N+1-x symmetry. And if we want to calculate the number of such permutations for given N, then there is an easy recursion: u[N]=sum(i=2,N,2,binomial(N-1,i-1)*u[i-1]*u[N-i]) where we sum only on even i values, the idea behind this is that see where you can place N, then the N length breaks up to i-1 and N-i length. Notice that it is possible that some numbers from [1,n] will still remain so in the end we just multiple by N!.
Used also the little Fermat theorem: 1/x==x^(p-2) mod p.
Overall interesting, but hard problem.

``````class Solution{

#define mod 1000000007
private: vector<int> fact;
public:

int powmod(int base,int expo,int m){

int ret=1,mult=base;
while(expo){
if(expo&1) ret=((long)ret*mult)%m;
mult=((long)mult*mult)%m;
expo>>=1;
}
return ret;
}

int inv(int x) { return powmod(x,mod-2,mod); }

int binom(int n,int k){

int mult=((long)fact[k]*fact[n-k])%mod;
return ((long) inv(mult)*fact[n])%mod;
}

int sequence(int n,vector<int> A,vector<int> B){

fact.resize(n+1);
vector<long> u(n+1);

fact[0]=1;
for(int i=1;i<=n;i++)fact[i]=((long)i*fact[i-1])%mod;

u[0]=1;
u[1]=1;
// for u: a[1]<a[2]>a[3]<a[4]>a[5]<a[6]
for(int N=2;N<=n;N++){
long sum=0;
for(int i=2;i<=N;i+=2)
// sum+=binomial(N-1,i-1)*u[i-1]*u[N-i]
sum=(sum+(long)binom(N-1,i-1)*((u[i-1]*u[N-i])%mod))%mod;
u[N]=sum;
}

vector<bool>inc(n+2,false),dec(n+2,false);
for(int p:A)inc[p]=true;
for(int p:B)dec[p]=true;

for(int i=1;i<=n;i++){
if(dec[i] && inc[i]) return 0;
if(dec[i] && dec[i+1]) return 0;
if(inc[i] && inc[i+1]) return 0;
}

int N=n;
long ans=1;
for(int i=1;i<=n;){
int len=0;
while(i<=n && (dec[i]||inc[i])) {len++;i++;}
if(len>0){
len+=2;
long mult=(binom(N,len)*u[len])%mod;
ans=(ans*mult)%mod;
N-=len;
}
else i++;
}
ans=((long) ans*fact[N])%mod;

return ans;
}};

int main(void){

Solution *s=new Solution;

cout<<s->sequence(4,{2},{3})<<endl;

cout<<s->sequence(10,{2,4,9},{3,8})<<endl;

return 0;
}
/*
output
5
100800
*/``````
by Expert (46,090 points)