Problem Description

近期B廠組織了一次大搬家，所有人都要按照指示換到指定的座位上。指示的內(nèi)容是坐在位置i上的人要搬到位置j上。現(xiàn)在B廠有N個(gè)人，一對一到N個(gè)位置上。搬家之后也是一一對應(yīng)的，改變的只有位次。 在第一次搬家后，度度熊由于疏忽，又要求大家按照原指示進(jìn)行了一次搬家。于是，機(jī)智的它想到：再按這個(gè)指示搬一次家不就可以恢復(fù)第一次搬家的樣子了。于是，B廠史無前例的進(jìn)行了連續(xù)三次搬家。 雖然我們都知道度度熊的“機(jī)智”常常令人堪憂，但是不可思議的是，這回真的應(yīng)驗(yàn)了。第三次搬家后的結(jié)果和第一次的結(jié)果完全相同。 那么，有多少種指示會讓這種事情發(fā)生呢？如果兩種指示中至少有一個(gè)人的目標(biāo)位置不同，就認(rèn)為這兩種指示是不相同的。

Input

第一行一個(gè)整數(shù)T，表示T組數(shù)據(jù)。 每組數(shù)據(jù)包含一個(gè)整數(shù)N(1≤N≤1000000)。

Output

對于每組數(shù)據(jù)，先輸出一行 Case #i: 然后輸出結(jié)果，對1000000007取模。

Sample Input Copy 2 1 3 Sample Output Copy Case #1: 1 Case #2: 4

AC代碼：

數(shù)組要用long long開，否則會出錯(cuò) #include<iostream> #include<cstdio> using namespace std; long long a[1000010]; void f(){a[1]=1,a[2]=2;for(int i=3;i<1000001;i++)a[i]=(a[i-1]+(i-1)*a[i-2])%1000000007; } int main() {int T,N;int i;while(cin>>T){f();for(i=0;i<T;i++){cin>>N;printf("Case #%d:\n%d\n",i+1,a[N]);}}return 0; }

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的大搬家的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。