UVALive 5971(LA 5971) Permutation Counting 동적 계획(배제 원리 시간 초과)

제목 대의:
정수 1부터 n까지 배열을 하는데 최종 배열 결과에 i+1이 i의 뒷자리에 딱 맞지 않으면 이 배열은 good이다. 정수 1부터 n까지 몇 가지 다른 배열 방식이 good의 배열이냐고 묻는다.
대략적인 사고방식:
이 문제는 한눈에 용척원리인 줄 알았는데 n이 10^6에 이르는 것을 발견했습니다. 그래서 앞서 쓴 용척원리는 당연히 TLE 였습니다.
나중에 최적화인가 TLE인가 생각을 해봤는데...10^4 Case가 있다는 걸 몰랐는데...
나중에 생각해 보니 dp밖에 안 된다고 생각해서 다음 dp가 점차적으로 밀어내는 식이 생겼다.
dp[n]로 1부터 n까지의 good 배열수를 표시하다
그러면 dp[n+1]에 대해 우리는 먼저 1부터 n선까지 배열하고 n+1을 삽입한 다음에 good의 배열을 고려한다. 만약에 1부터 n까지 good의 배열이 되면 n+1을 추가하면 n의 빈자리에 삽입할 수 있다(원래 good로 배열된 n의 뒤에 놓을 수 없다) 이렇게 n*dp[n]가 있다.
또 다른 가능성은 원래 1부터 n까지의 배열에 유일하게 인접한 i와 i+1이 존재한다는 것이다. 우리는 n+1을 이 두 수 사이에 삽입하여 인접 상태를 깨고 good 배열이 된다. 이렇게 하면 유일하게 인접한 쌍이 존재하는 배열에 대해 1개의 위치만 선택할 수 있다. 이런 배열의 개수는 C(1, n-1)*dp[n-1]이다. i와 i+1은 C(1, n-1)의 선택이 있기 때문이다.그러나 각 선택이 서로 인접한 후에 서로 인접한 것을 하나의 전체로 간주하고 다른 것은 서로 인접할 수 없다. n-1개수의 good 배열수에 해당하기 때문에 (n-1)*dp[n-1]종이 가능하다.
이렇게 하면 점진식이 나온다.
dp[n + 1] = n*dp[n] +(n - 1)*dp[n - 1]
그 중에서 dp[1]=1, dp[2]=1;
먼저 모든 dp[k]를 미리 처리한 다음 검색 출력 시간의 복잡도는 O (N + T) 이다
코드는 다음과 같습니다.
Result  : Accepted     Memory  :  0 KB     Time  :  49 ms

/*
 * Author: Gatevin
 * Created Time:  2014/8/3 13:48:36
 * File Name: test.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

lint dp[1000100];
const lint mod = 1000000007LL;

int main()
{
    int t;
    int n;
    dp[1] = 1LL;
    dp[2] = 1LL;
    dp[3] = 3LL;
    for(int i = 4; i <= 1000000; i++)
    {
        dp[i] = (((i - 1) * dp[ i - 1]) % mod + (( i - 2) * dp[ i - 2]) % mod) % mod;
    }
    cin>>t;
    for(int cas = 1; cas <= t; cas++)
    {
        cin>>n;
        cout<<"Case "<<cas<<": "<<dp[n]<<endl;
    }
    return 0;
}

순조롭게 쓰여졌는데 끊어진 용척원리...
사상:Ai={숫자 i와 i+1이 연결됨) 용척은 간단하지만 이 문제의 데이터 범위는 분명히 시간을 초과할 것이다
Result  :  Time Limit Exceeded

/*
 * Author: Gatevin
 * Created Time:  2014/8/3 12:40:25
 * File Name: test.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

const lint mod = 1000000007LL;

lint A[1000100];
int n;

lint quick_pow(lint base, lint pow)
{
    lint ret = 1;
    while(pow)
    {
        if(pow&1)
        {
            ret = (ret*base) % mod;
        }
        base = (base * base) % mod;
        pow >>= 1;
    }
    return ret;
}

lint getc(lint a, lint b)
{
    if(a < b) return 0;
    if(b > a - b) b = a - b;
    lint s1 = 1;
    lint s2 = 1;
    for(int i = 0; i < b; i++)
    {
        s1 = (s1*(a - i)) % mod;
        s2 = (s2*(i + 1)) % mod;
    }
    return s1*quick_pow(s2, mod - 2) % mod;
}

lint lucas(lint a, lint b)
{
    if(b == 0) return 1;
    return getc(a % mod, b % mod) * lucas(a / mod, b / mod) % mod;
}

lint solve()
{
    lint answer = 0;
    int sign = 1;
    for(int i = 0; i <= n - 1; i++)
    {
        if(i & 1)
        {
            sign = -1;
        }
        else
        {
            sign = 1;
        }
        lint tmp = lucas(n - 1, i);
        answer = (answer + (sign*(tmp*A[n - i]) % mod + mod) % mod) % mod;;
    }
    return answer;
}


int main()
{
    int t;
    A[1] = 1;
    A[0] = 1;
    for(int i = 2; i <= 1000000; i++)
    {
        A[i] = (A[i - 1] * i) % mod;
    }
    cin>>t;
   for(int cas = 1; cas <= t; cas++)
   {
      cin>>n; 
      cout<<"Case "<<cas<<": "<<solve()<<endl;
   }
    return 0;
}

최적화된 버전은 붙이지 않겠지..