Untitled
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); }