SRM565 Div1 Medium(500) TheDivisionGame

TopCoder

TheDivisionGame

重複を許した素因数の個数がGrundy数となる。よって、P[i]をiの重複を許した素因数の個数として、Pの連続した部分列でxorした結果が0ではないものを数えれば良い。

各iについてP[i]を求めると間に合わないが、各素数pについてpの整数倍のP[i]をインクリメントしていけば間に合う。部分列の個数は、動的計画法で、xorした値ごとに部分列の個数を覚えておく。

#include <vector>
#include <numeric>
using namespace std;

//  エラトステネスの篩
//  V[i]にiが素数かどうかを格納した配列を返す（i<n）
vector<bool>eratosthenes(int n){
    vector<bool>v(n,true);v[0]=v[1]=false;
    for(int i=2;i<n;i++)if(v[i])for(int j=i+i;j<n;j+=i)v[j]=false;
    return v;}

class TheDivisionGame{public:
long long countWinningIntervals( int L, int R )
{
    int n = R-L+1;

    int N = 100000;
    vector<bool> E = eratosthenes(N);

    //  P[i]: L+iの重複を含めた素因数の個数
    vector<int> P(n);
    vector<int> S(n,1);

    for ( int p=0; p<N; p++ )
    if ( E[p] )
        for ( long long f=p; f<=R; f*=p )
            for ( long long i=(L-1)/f*f+f; i<=R; i+=f )
                P[int(i-L)]++,
                S[int(i-L)] *= p;
    for ( int i=L; i<=R; i++ )
        if ( S[i-L]<i )
            P[i-L]++;

    //  T[i]: P[k]^P[k+1]^… がiとなるkの個数
    int M = 32;
    vector<long long> T(M);
    long long ans = 0;
    for ( int i=0; i<n; i++ )
    {
        vector<long long> B = T;
        T = vector<long long>(M);
        for ( int j=0; j<M; j++ )
            T[j] += B[j^P[i]];
        T[P[i]] += 1;
        ans += accumulate(T.begin()+1,T.end(),0LL);
    }

    return ans; 
}};