HDU3693 Math Teacher's Homework ---- 数位DP

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

HDU3693 Math Teacher's Homework

一句话题意

给定$n, k以及m_1, m_2, m_3, ..., m_n$求$x_1 \oplus x_2 \oplus x_3 \oplus ... \oplus x_n == K(x_1 \leq m_1, x_2 \leq m_2...)$ 的方案数。

题解

一开始口糊了一下，然后写代码的时候发现不少东西没考虑周到，于是就看起了题解。

我们首先需要发现一个重要的性质：

如果某一位上不受m限制（也就是选0或选1都可以）那么无论其它数的这一位位选什么都可以通过这一位来变成结果和K的这一位相等

为了避免来自$x <= m$的麻烦，我们首先让$m ++$，使条件变为$x < m$。

然后按照数位dp的套路对位分析。

首先假设我们处理到了第j位，然后从高位到$j + 1$位都已经到了最大值

然后第$j$位由于要小于m，所以m的这一位必然1,然后j的这一位必然是0

然后按照套路我们发现如果这一位我们选了0,那么后面的位随便选都不会大于m

为了方便dp，我们令每一位最早允许随便选的那个$x_i$为$A_j$，这个数将在后面被限制以使其它自由位达到K上对应位的要求

我们记第j位上的第i个数字为自由的，当且仅当这个位不是被m限制了（即第i个数从高位枚举到第一个比m小的位置），且不是那些被最早选择（上一行的定义）限制的数字。

然后每一位上的方案数就是$2^{自由数个数-1}$

于是我们设$dp[i][j][0/1]$表示第i个数的“第i个数从高位枚举到第一个比m小的位置”为j，此位的异或值为0/1

下面我们记

$num[i][j]$为第i个数字第j位

$sum[i][j]$为j位上从第一个数字异或到第i个数字的结果

然后分情况（自由数位置）讨论从状态$dp[i - 1][k][r]$（注意大小写）（注意下面$2^x$的下标）转移，若

m此位可以有不同限制，即$num[i][j] == 1$

$j < k$：$dp[i][j][sum[i - 1][j]] += dp[i - 1][k][r] * 2^k$

$j > k$：$dp[i][k][r \oplus sum[i - 1][j]] += dp[i - 1][k][r] * 2^j$

$j == k$：$dp[i][j][r] += dp[i - 1][k][r] * 2^k$

最后要求$k[j] == sum[n][j]$的时候才能统计入答案

（然而我并不知道怎么用Latex打出'^' ......）

代码如下：

 #include <cstdio>

 #include <bitset>

 #include <cstring>

 using namespace std;

 char buf[], *pc = buf;

 inline void Main_Init(){

     static bool inited = false;

     if(inited) fclose(stdin), fclose(stdout);

     else {

         fread(buf, , , stdin);

         inited = true;

     }

 }

 inline int read(){

     int num = ;

     char c;

     while((c = *pc ++) < );

     while(num = num *  + c - , (c = *pc ++) >= );

     return num;

 }

 //Source Code

 const int MAXN = ;

 const int MAXM = ;

 const int MODS = ;

 int n, ans;

 int x[MAXN];

 unsigned int bin[MAXM];

 int dp[MAXN][MAXM][];

 bitset<> K, num[MAXN], sum[MAXN];

 int main(){

     Main_Init();

     for(int i = ; i < ; i++) bin[i] =  << i;

     while(n = read(), n){

         K = read();

         for(int i = ; i <= n; i++)

             num[i] = x[i] = read() + ;

         memset(sum, , sizeof(sum)), memset(dp, , sizeof(dp));

         ans = ;

         dp[][][] = ;

         for(int j = ; j < ; j++) sum[][j] = num[][j];

         for(int i = ; i <= n; i++)

             for(int j = ; j < ; j++)

                 sum[i][j] = sum[i - ][j] ^ num[i][j];

         for(int i = ; i <= n; i++){

             for(int j = ; j < ; j++){

                 if(!num[i][j]) continue;

                 for(int k = ; k < ; k++){

                     for(int r = ; r < ; r++){

                         if(dp[i - ][k][r]){

                             if(j > k) dp[i][j][sum[i - ][j]] = (dp[i][j][sum[i - ][j]] + 1ll * dp[i - ][k][r] * bin[k]) % MODS;

                             else if(j < k) dp[i][k][r ^ num[i][k]] = (dp[i][k][r ^ num[i][k]] + 1ll * dp[i - ][k][r] * bin[j]) % MODS;

                             else dp[i][j][r] = (dp[i][j][r] + 1ll * dp[i - ][k][r] * bin[k]) % MODS;

                         }

                     }

                 }

             }

         }

         for(int i = ; i >=  && K[i + ] == sum[n][i + ]; i--)

             ans = (1ll * ans + dp[n][i][K[i]]) % MODS;

         printf("%d\n", ans);

     }

     Main_Init();

     return ;

 }