大搬家
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem's Link: http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=584&pid=1001
Mean:
略
analyse:
找规律，必须两次就恢复回去，必须一对一对换，或两对两对换等。
Time complexity: O(n)
Source code:
/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-05-23-18.04 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #define LL long long #define ULL unsigned long long using namespace std; const int mod=1000000007; const int MAXN=1000010; ULL ans[MAXN]; void pre() { ans[1]=1,ans[2]=2; for(int i=3;i<MAXN;++i) { ans[i]=ans[i-1]+(i-1)*ans[i-2]; ans[i]%=mod; } } int main() { int t; pre(); scanf("%d",&t); int Cas=1; while(t--) { int n; scanf("%d",&n); printf("Case #%d:\n",Cas++); printf("%d\n",ans[n]); } return 0; } /* */
