Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
532 B
0
Indexable
Never
#define MOD 1000000007
#include<vector>

long long int der(int n,vector<long long int> &dp){ //top down dp
    if(n==1) return 0;
    if(n==2) return 1;

    if(dp[n]!=-1) return dp[n];


   // int ans=((  (der(n-1,dp)%MOD) + (der(n-2,dp)%MOD) ) * ((n-1)%MOD) %MOD);
    long long int ans =(((n-1)%MOD) * ((der(n-1,dp)%MOD) +(der(n-2,dp) %MOD))%MOD);
    return dp[n]=ans;



}
long long int countDerangements(int n) {
    // Write your code here.
    vector<long long int> dp(n+1,-1);
    return der(n,dp);
}