250pt：
题意：有最长N=17的一条格子，每个格子是W、B和R三种颜色之一，当某个格子上有兔子时，下一个回合该兔子按照以下的规则移动：
如果兔子在第一个格子，则向右移动一格；
否则如果兔子在倒数两个格子，则向左移动一格；
否则如果兔子在W格上，则向左移动一格；
否则如果兔子在B格上，则向右移动一格；
否则兔子在R格上，如果是它第一次移动，则向左移动一格，否则回到上一步过来的地方。
每一轮每个兔子移动，然后最后一个格子消失，如果某个格子上有多于一只兔子，则这个格子上的兔子消失。整个过程一直持续到总格子数等于2为止。现在在N个格子里面初始随机放R只兔子，问最后期望剩下几只兔子。
思路：模拟几个你会发现因为每回奇数位置的要跳到偶数位置，反之也一样。所以答案必然跟奇偶性有关系
很明显，奇数上的会相互抵消，偶数也一样。所以统计就很简单了。再者枚举一下初始位置即可。
code：
#line 7 "RabbitStepping.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std; #define PB push_back
#define MP make_pair #define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i)
#define two(i) (1 << i)
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII; class RabbitStepping
{
public:
double getExpected(string field, int r)
{
int n = field.size();
int a, b;
double ret = ;
for (int i = ; i < two(n); ++i){
a = b = ;
for (int j = ; j < n; ++j) if (two(j) & i){
if (j & ) ++a;
else ++b;
}
if (a + b == r) ret += (a & ) + (b & );
}
for (int i = ; i <= r; ++i)
ret = ret / (n - i + 1.0) * (i + .);
return ret;
}
};
500pt
题意：第一年7月天上掉下一对小兔子；之后:
每年3月，老兔子生一对小兔子，原来的小兔子升级为老兔子；
某些年的11月，消失一半兔子，消失的兔子总是年龄较大的那些。
现在给定最多50个兔子会消失一半的年份，问第K<=10^7年的12月一共有多少兔子。答案模MOD=1,000,000,009。
思路：如果没有消失这一说，那么答案就是一个斐波那契数列。那就难在如何处理消失的。
而且每次%MOD后，再处理消失便会出问题。所以我们必须要用另外一个来记录奇偶性。
由于最多消失50次，也就是说最多有50次的/2操作。那么我们直接记录下当前答案%2^50的结果便可直到奇偶性。。
接下来直接模拟就行了。注意奇偶分开操作就行
code:
#line 7 "RabbitIncreasing.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std; #define PB push_back
#define MP make_pair #define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i)
#define M 1000000009
#define P (1LL << 51)
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII; class RabbitIncreasing
{
public:
long long power(long long a, int b){
long long ret = ;
for (;b > ; b >>= ){
if (b&) ret = (ret * a) % M;
a = (a * a) % M;
}
return ret;
}
int getNumber(vector <int> leave, int k)
{
sort(leave.begin(), leave.end());
int T2 = power(, M - );
long long cur = , pre = , next;
long long a = , b = , c;
long long dec, tmp;
if (leave[] == ) return ;
int l = , n = leave.size();
for (int i = ; i <= k; ++i){
next = (cur + pre) % M;
c = (a + b) % P;
if (l < n && leave[l] == i){
if (c & ){
dec = (c + ) / ;
c /= ;
a = (a - dec + P) % P;
tmp = ((next + ) * T2) % M;
cur = (cur - tmp + M) % M;
next = (next - tmp + M) % M;
}else {
dec = c / ;
c /= ;
a = (a - dec + P) % P;
tmp = (next * T2) % M;
cur = (cur - tmp + M) % M;
next = (next - tmp + M) % M;
}
++l;
}
pre = cur, cur = next;
b = a, a = c;
}
return cur;
}
};