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 <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

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<<dp[n][0]<<endl;

    }

    return 0;

}

巴特西

HDOJ 4689 Derangement DP

Derangement

最新文章

热门文章