Hihocoder 1259 A Math Problem(數位DP+公式推導)

2015北京區域賽 K.A Math Problem

題目傳送門

提及傳送門

UVA送出會RE，no why!

題意

定義一個集合，集合的函數映射為：

f(n)=⎧⎩⎨f1=1,3fn×f2n+1=f2n×(1+3fn),n=1 (1)n>1 (2)

定義 [1,n] 中的任意數字為 si ，然後規定 g(x) 為 [1,n] 中令 f(si)%k==x 的 si 的個數.

求 g(x) 異或的結果

解題思路

将 (2) 簡化得到 3fn×(f2n+1−f2n)=f2n ，由于 f1=1 ，是以 f2n+1−f2n>0 .

然後将 fan<6fn 帶入 (2) 中可以得到 3fn×(f2n+1−f2n)<6fn 得到 f2n+1−f2n<2 ，是以 f2n+1−f2n=1 ，是以 f2n+1=f2n+1 ,将這個式子帶入 (2) 中可以得到如下倆個等式

f2n=3fn

f2n+1=3fn+1

接下來我們可以發現，對于目前這個數我們可以進行兩種操作：

1. m 為奇數的時候，一定可以表達為fm=3×fm−12+1
2. 偶數時則是 fm=3×fm2+1 .

當我們第一個操作完後，接下來我們要進行第一步操作還是第二步操作取決于目前的奇偶，即二進制目前位是 1 還是0，這樣我們就将 fn 變為如下等式：

fn=2_bitx×3x+2_bitx−1×3x−1+...+2_bit0×30

其中 2_bitx 表示 n 轉換為二進制時的每一位.

然後我們就可以用數位DP來處理了，數組定義如下：

Rsum[i]:表示目前餘數為 i 的數的個數

dp[x][y]:表示到達目前位置得到的餘數為 y 的個數是多少

P[x]:用來預處理出每一位需要乘上多少個 3

vis[x]:用來标記目前位置是否一定通路過了

bit[x] :用來儲存 n <script type="math/tex" id="MathJax-Element-5455">n</script>的每一位

代碼

#include <cstdio>
#include <cstring>
#include <algorithm>


using namespace std;

typedef long long LL;
const int WS =  + ;
const int REM =  + ;

LL n, dp[WS][REM], P[WS], Rsum[REM];
bool vis[WS];
int bit[WS], sz, k;

void pinit() {
    sz = ;
    memset(dp, , sizeof(dp));
    memset(Rsum, , sizeof(Rsum));
    memset(vis, false, sizeof(vis));
    P[] = ;
    for(int i = ; i < WS; i ++) {
        P[i] = P[i - ] *  % k;
    }
}

void DFS(int pos, int remainder, int limit) {
    if(pos < ) {
        Rsum[remainder] ++;
        return ;
    }
    //此處不再是用正常的dp[pos]...去标記是否通路的原因是，目前狀态具有多種，即reaminder對餘數個數的影響不同
    if(!limit && vis[pos]) {
        remainder = remainder * P[pos + ] % k;
        for(int i = ; i < k; i ++) {
            Rsum[(remainder + i) % k] += dp[pos][i];
        }
        return;
    }
    int ends = limit ? bit[pos] : ;
    for(int i = ; i <= ends; i ++) {
        DFS(pos - , (remainder *  + i) % k, limit && i == ends);
    }
    if(!limit) {
        vis[pos] = true;
        for(int i = ; i < k; i ++) {
            dp[pos][i] = Rsum[i];//目前位置的狀态即是Rsum[i]
        }
    }
}

void solve() {
    pinit();
    int len = ;
    while(n) {
        bit[len ++] = n % ;
        n >>= L;
    }
    if(len == ) len ++;
    DFS(len - , , );
    Rsum[] --;//清除0對資料的影響
    LL ans = ;
    for(int i = ; i < k; i ++) {
        ans ^= Rsum[i];
    }
    printf("%lld\n", ans);
}

int T;

int main() {
    scanf("%d", &T);
    while(T --) {
        scanf("%lld%d", &n, &k);
        solve();
    }
    return ;
}