UVALive 5971 Permutation Counting 组合学、递推

Permutation Counting 组合学、递推

Source

UESTC 2016 Summer Training #11 Div.2

UVALive 5971

My Solution

反正枚举全排列必定TLE的， 然后排列组合里面其实递推挺多的， 也可以搞出前几项， 然后去 数列网站上查一下

这里的递推式是 dp[i] = dp[i - 1] * (i - 1) + dp[i - 2] * (i - 2)

这里dp[i] 表示 n == i 时合法的排列数

1）对于 dp[i - 1] * (i - 1) 则是对于 n == i - 1的合法排列， 可以在 (i - 1)个地方把第i个数插进去就好了， 总共 (i - 1 + 1) - 1个位置;

2）对于dp[i - 2] * (i - 2)则因为对于 n == i - 1的一些不合法序列， 插入一个i其实也可以变成dp[i]的一个合法序列，

比如对应dp[i - 1] 其中的不合法序列中有一个 ......1 2, 其它地方合法， 那么把i插入到 1 2 之间， 变成 ........ 1 i 2 就合法了，

那这样只有一个地方pair不合法的 n == i - 1 的个数刚好是 dp[i - 2] * (i - 2)]的个数， 也就是把那个不合法的pair看成一个数

也就是对于dp[i - 2]的每一种情况， 取x 然后把x+1 用i - 1换出来， 然后把x + 1 放到x 后面, 然后把 i 放到x 和 x+1之间有 i- 2个位置可以这么做

所以dp[i - 2] * (i - 2)]

复杂度 O(n) 预处理 T*O(1)查询

#include 
#include 

using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;
const LL Hash = 1000000007;

LL dp[maxn];

inline LL mod(LL x)
{
    return x - x/Hash*Hash;
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    #endif // LOCAL
    dp[1] = 1; dp[2] = 1; dp[3] = 3;
    for(int i = 4; i < maxn; i++)
        dp[i] = mod( mod(dp[i - 1]*(i - 1)) + mod(dp[i - 2]*(i - 2)) );

    int T, n, kase = 0;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        printf("Case %d: %lldn", ++kase, dp[n]);

    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx