Derangement

Time Limit: 7000/7000 MS (Java/Others) Memory Limit: 65535/102400 K (Java/Others)
Total Submission(s): 846 Accepted Submission(s): 256

Problem Description A derangement is a permutation such that none of the elements appear in their original position. For example, [5, 4, 1, 2, 3] is a derangement of [1, 2, 3, 4, 5]. Subtracting the original permutation from the derangement, we get the derangement difference [4, 2, -2, -2, -2], where none of its elements is zero. Taking the signs of these differences, we get the derangement sign [+, +, -, -, -]. Now given a derangement sign, how many derangements are there satisfying the given derangement sign?
Input There are multiple test cases. Process to the End of File.
Each test case is a line of derangements sign whose length is between 1 and 20, inclusively.
Output For each test case, output the number of derangements.
Sample Input

+-
++---

Sample Output

1
13

Author Zejun Wu (watashi)
Source 2013 Multi-University Training Contest 9

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef long long int LL; LL dp[50][50]; char str[50]; int main() { while(cin>>str) { if(str[0]=='-') { puts(0); continue; } memset(dp,0,sizeof(dp)); int n=strlen(str); dp[1][1]=1; for(int i=2;i<=n;i++) { for(int j=0;j<=i;j++) { if(str[i-1]=='+') { if(j) dp[i][j]+=dp[i-1][j-1]; dp[i][j]+=dp[i-1][j]*j; } else if(str[i-1]=='-') { dp[i][j]+=dp[i-1][j]*j; dp[i][j]+=dp[i-1][j+1]*(j+1)*(j+1); } } } cout<
      
       ?
       ?

HDOJ 4689 Derangement DP

Derangement