SRM475 Div1 Medium(600) RabbitIncreasing

RabbitIncreasing

わからなかったので、あちこちのブログなどを参考に。剰余で計算していると、ドナドナされる番数が２才以上の番数よりも多ければ〜という比較と、偶奇の判定ができない。１年目以外は２才以上の番は子供を産むので、２才以上の番を消して、１才の番を半分にすれ良い。また、偶奇の判定は2⁵⁰の剰余（実際はオーバーフローに任せられる）を覚えておけば良い。なるほど。

#include <vector>
#include <algorithm>

using namespace std;

class RabbitIncreasing
{
public:
    int getNumber( vector <int> leaving, int k );
};

int RabbitIncreasing::getNumber( vector <int> leaving, int k )
{
    typedef unsigned long long ull;

    const ull M  = 1000000009;
    const ull M2 =  500000005;  //  1/2

    ull c0m = 0,  c0b = 0;      //  0才の番
    ull c1m = 0,  c1b = 0;      //  1才の番
    ull c2m = 0,  c2b = 0;      //  2才以上の番

    for ( int y=1; y<=k; y++ )
    {
        //  3月
        c0m = c2m,  c0b = c2b;

        //  7月
        if ( y == 1 )
            c0m++,  c0b++;

        //  11月
        if ( find( leaving.begin(), leaving.end(), y ) != leaving.end() )
        {
            if ( y == 1 )
                c0m = 0,  c0b = 0;
            else
            {
                if ( c1b % 2 == 0 )
                    c1m = c1m * M2 % M;
                else
                    c1m = ( c1m + M - 1 ) * M2 % M;
                c1b /= 2;

                c2m = 0,  c2b = 0;
            }
        }

        //  12月
        c2m = ( c2m + c1m ) % M,  c2b += c1b;
        c1m = c0m,  c1b = c0b;
        c0m = 0,  c0b = 0;
    }

    return ( c0m + c1m + c2m ) % M;
}