XORが0となる数列は何通りあるか？という問題が解けない

Question

競プロの問題で質問です。

長さNのK以下の数列で、XORを取ったものが0となる数列は何通りあるでしょうか。

たとえば、N=3, K=2のとき、(0, 0, 0), (0, 1, 1), (0, 2, 2), (1, 0, 1), (1, 1, 0), (2, 0, 2), (2, 2, 0) の7通りが答えです。

という問題を解きたいのですが、解くことができません。どのようにすれば解けるでしょうか？制約は N ≦ 1000, K ≦ 2^50 です。

追記

考えたことを追記します。

①__長さNのK以下の数列のXORが0の通り数__ （求めたいもの）
②__長さN-1のK以下の数列のXORがK以下の通り数__
③__長さN-1のK以下の数列のXORがKを超える通り数__

①と②は等しいです。
なぜなら、②のXORの結果と同じ数値を後ろに付け足せば、①の数列になるからです。
そして、③は②の余事象であるため、③を求めることを考えました。
以下のようなDPを考えます。

dp[i][j] := 上からiビット目まで見たときの通り数（jはKを超えたかどうか）

そして次のようなコードを書きました。
（オーバーフローは気にしない方向でお願いします）

#include <bits/stdc++.h>
using namespace std;

int dp[52][2];

int comb(int x,int y){
    if(x<0||y<0||x<y)return 0;
    int r=1;
    for(int i=1;i<=y;++i){
        r*=(x-i+1);
        r/=i;
    }
    return r;
}

int main(){
    int N;
    long long K;
    cin>>N>>K;

    int k=0;
    long long kk=K;
    while(kk)k++,kk>>=1;

    int odd=0,even=0;
    for(int i=1;i<=N-1;i+=2){
        odd+=comb(N-1,i);
    }
    for(int i=0;i<=N-1;i+=2){
        even+=comb(N-1,i);
    }

    dp[0][0]=1;
    for(int i=0;i<k;++i){
        for(int j=0;j<=1;++j){
            if(j==1){
                dp[i+1][j]+=dp[i][j]*(even+odd);
            }else{
                if((K&(1LL<<(k-i-1)))==0){
                    dp[i+1][1]+=dp[i][j]*odd;
                    dp[i+1][0]+=dp[i][j]*even;
                }else{
                    dp[i+1][j]+=dp[i][j]*odd;
                }
            }
        }
    }
    cout<<pow(K+1,N-1)-dp[k][1]<<endl;
    return 0;
}

しかしこのコードでは、数列の最後の要素がKを超えた場合が考慮されていません。
たとえばN=3、K=2のとき、(1, 2, 3), (2, 1, 3)まで数えてしまうため、出力は5です。
どのように書き換えれば 数列の要素がKを超えた場合 を考慮できるかわからず、解決の糸口が見つからなかったため質問いたしました。

追記2

できればヒントだけでも教えていただけると嬉しいです。
ある程度の行間であれば頑張って対応いたします。
回答よろしくお願いします。

Comments

[cateye]

>解くことができません・・・何処までやったか、途中でいいのでソース貼り付けて下さい。でないと、丸投げになります。
また、環境（OSやコンパイラなど）も教えて下さい。

[dodox86]

どこで提示されている問題でしょうか。今、競技開催中な訳ではないですよね。

[xebme]

群論と関係ありますか？

[xebme]

群論とは関係ありません。まず冪集合から見ていく。

[xebme]

変なこと言ってごめんなさい。何通りとは数だけいえばよいですか？列挙できないですよね。

[toshiyan]

列挙は難しいです。通り数は軽く10億を超えます…。

[xebme]

2 ≦ N かつ 2^0 ≦ K ですか。K+1 が 2^m のとき②がなさそうですね。

[toshiyan]

②ではなくて③な気がします。間違っていたらすみません…。

[xebme]

③です。XOR計算せずに数列でできないか（③の件数が割り出せればね）

Answer 1

解決しましたのでコードを載せます。回答してくださった方々ありがとうございました！！

#include <bits/stdc++.h>
using namespace std;

int dp[60][1010];

int comb(int x,int y){
    if(x<0||y<0||x<y)return 0;
    int r=1;
    for(int i=1;i<=y;++i){
        r*=(x-i+1);
        r/=i;
    }
    return r;
}

int pow2(int n){
    int ret=1;
    while(n>0)ret*=2,--n;
    return ret;
}

int main(){
    int N;
    long long K;
    cin>>N>>K;

    int D=0;
    long long kk=K;
    while(kk)D++,kk>>=1;

    dp[0][0]=1;
    for(int i=0;i<D;++i){
        for(int j=0;j<=N;++j){
            if(!(K&(1<<(D-i-1)))){
                dp[i+1][j]+=dp[i][j]*pow2(j-1);
                continue;
            }
            for(int k=0;k<=N-j;++k){
                if(j==0&&(N-k)%2)continue;
                dp[i+1][j+k]+=dp[i][j]*comb(N-j,k)*pow2(j-1);
            }
        }
    }
    int ans=0;
    for(int i=0;i<=N;++i)ans+=dp[D][i];
    cout<<ans<<endl;
    return 0;
}

解説pdf

Answer 2

前提
「K以下の数列のXORがKを超える」とその時点で、その数列の作成は終了する
これが正しければ、損失ゲーム（価値割引）ではないかと思います。

発見
K+1 = 2^m のとき③は起きないので、通り数は、(K+1)^(N-2) (これ計算できますか？)

損失
K=2 のとき、③は２件、②は７件
１回 XOR をとると (2+1)(2+1) のうち 2 件失う。
一般化すると、１回 XOR をとると (K+1)(K+1) のうち Z 件失う。K にたいして Z はそれぞれ一定の数。
(K+1 = 2^m のとき Z=0)

K	1	2	3	4	5	6	7
Z	0	2	0	6	8	6	0

K から Z を計算する方法が見つかれば解決。

((K+1)*(K+1) - Z) * (K+1) - Z ...

だめですね。２段階目以降は工夫しないとうまくいきません。

追記1

マイナスをたくさんいただきましたので、ない知恵を絞って少し前進。

k=2の場合の分析

N	1	2	3	4	5
X ②+③	9	21	51	123	297	X(n)=R(n-1)*(k+1)
Z ③	2	4	10	24	58	Z(n)=f( rx(n-1), k)
R ①=②	7	17	41	99	239	R(n) = X(n) - Z(n)
Rの内訳 0 (r0)	3	7	17	41	99	r0(n)=R(n-1)
Rの内訳 0以外 (rx)	4	10	24	58	140

r0(n)=R(n-1)なのは質問内容からもあきらかです。
N-1 のときの R が求める数です。
0 から K を超える数は生じない。0 XOR a = a
0 を超える数から K を超える数が生じる。それをつくる関数を f としておきます。

f( rx(n-1), k) を求めたい。

• k=2のとき、rx(n-1)
• k+1=2^m のとき 0

Comments

[npkk]

競技プログラミングがどういうものか調べてから回答された方がよろしいかと思います。回答が文脈に適合していません。

[xebme]

アドバイスありがとうございます。勉強して出直します。質問者様、大変失礼いたしました。

Answer 3

ヒントだけでも良いとの事なので置いておきます。
なんとなく再帰処理っぽい気はするのですが……。

【追記】
表は[4,0,1,5]とかを、4015(７進数)などに見立てて数を調べた結果です。
プログラムは以下。

'注意：下手にketaとかsinsuに大きな数字(10以上とか)を入れると、あっという間に固まります。
Sub Macro1()
    Dim keta As Double
    Dim sinsu As Double
    Dim ans As Double
    
    Dim i As Double
    Dim mstr_i As String
    Dim tmpsinsu As Double
    
    keta = 3
    sinsu = 4
    
    ans = 0
    i = 0
    While i < sinsu ^ keta
        mstr_i = S10_2(i, sinsu)
        tmpsinsu = 0
        mstr_i = Replace(mstr_i, "0", "")   '先に０を抜いとく
        While Len(mstr_i) Mod 2 = 0 And Len(mstr_i) <> 0
            mstr_i = Replace(mstr_i, CStr(tmpsinsu), "")
            tmpsinsu = tmpsinsu + 1
        Wend
        If Len(mstr_i) = 0 Then
            ans = ans + 1
        End If
        i = i + 1
    Wend
    
    MsgBox "sinsu=" & sinsu & " keta=" & keta & " ans=" & ans
End Sub

'10進→2進
Function S10_2(X As Double, sin As Double) As String
    Dim XX As Double
    Dim Y As String
    XX = X
    If (XX < 0) Then
        Y = "Error"
    Else
        Do
            Y = XX Mod sin & Y
            XX = XX \ sin
        Loop While (XX > 0)
    End If
    S10_2 = Y
End Function