[數值遞推]OI練習題：整理牙刷 put 解題報告

【問題描述】

衆所周知，XW同學早晨起來是要刷牙的。

XW同學有 N 支牙刷，又有 N 個牙刷套 , 開始的時候，一支牙刷對應放在一個牙刷套中。可是有一天，XW同學把所有牙刷套裏的牙刷都拿出來，玩了一會兒，他又要把所有的牙刷都放回去。可是，他忽然一想，我可不可以使得沒有任何一支牙刷放回它原來的牙刷套裏面呢 ?

XW同學努力試了很久，卻一直沒有成功過一次。於是他斷定這個要求是無法達成的，你怎麼認爲的呢 ?

【輸入文件】

輸入文件 put.in 只包括一個整數 N ，表示牙刷和牙刷套的總數。

【輸出文件】

輸出文件 put.out ，如果存在滿足要求的方法，輸出放法方案總數 L 。因爲方案總數可能比較大，所以你可以將答案 Mod 1206 後再輸出。如果不存在滿足要求的方法，則輸出 "No Solution!”

【樣例輸入】

3

【樣例輸出】

2

【數據範圍】

對於 40 ％的數據，保證 N ≤ 9

對於 100 ％的數據，保證 N ≤ 100000

【分析】

就是一個公式，沒什麼好說的。

F[1]=0;

F[2]=1;

F[i]=(i-1)*(F[i-1]+F[i-2]) (i>=3)

注意同餘原理的應用。

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
unsigned long long F[100001];
int main()
{
    freopen("put.in","r",stdin);
    freopen("put.out","w",stdout);
    int N;
    scanf("%d\n",&N);
    F[1]=0;
    F[2]=1;
    for (int i=3;i<=N;i++)
        F[i]=((i-1)*(F[i-1]+F[i-2]))%1206;
    if(N<2)
        cout<<"No Solution!"<<endl;
    else
        cout<<F[N]<<endl;
    return 0;
}