ACM-ICPC 2018 徐州赛区网络预赛A Hard to prepare（DP）题解-白红宇

ACM-ICPC 2018 徐州赛区网络预赛A Hard to prepare（DP）题解

阅读量：7047 次

发布时间：2019-06-28

本文共 1506 字，大约阅读时间需要 5 分钟。

题意：有n个格子拉成一个环，给你k，你能使用任意个数的0 ~ 2^k - 1，规定操作 i XNOR j 为~（i ^ j），要求相邻的格子的元素的XNOR为正数，问你有几种排法，答案取模1e9 + 7。本题所使用的数字为无符号位数字。

思路：无符号位，所以异或取反后为正数，只可能是两个数相加不为2^k - 1。所以转化为相邻两个数之和不为2^k - 1的排法有几种（首尾也不能）。这个问题很像扇形涂色问题。我们开dp[ n ][ 3 ]记录到第i长时的三种情况：头尾和不为2^k - 1且头尾不相等，头尾相等，头尾和为2^k - 1。然后很好写出各自的转移方程。显然我们一共有元素2^k种，但是这个有个坑，就是我在用2^k - 1，2^k - 2时可能为负数，所以要+MOD % MOD。

代码：

#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                typedef long long ll;using namespace std;const int maxn = 1e6 + 10;const int seed = 131;const ll MOD = 1e9 + 7;const int INF = 0x3f3f3f3f;ll pmul(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans = ans * a % MOD; a = a * a % MOD; b >>= 1; } return ans;}ll dp[maxn][3]; //头尾无关 头尾相等 头尾值为0int main(){ int T; ll n, ans, k, fac, fac1, fac2, fac3; scanf("%d", &T); while(T--){ scanf("%lld%lld", &n, &k); fac = pmul(2, k); fac1 = (fac - 1 + MOD) % MOD; fac2 = (fac - 2 + MOD) % MOD; fac3 = (fac - 3 + MOD) % MOD; dp[1][0] = fac; dp[1][1] = 0; dp[2][0] = fac * (fac - 2 + MOD) % MOD; dp[2][1] = fac; dp[1][2] = fac; for(int i = 3; i <= n; i++){ dp[i][0] = (dp[i - 1][0] * fac3 % MOD + dp[i - 1][1] * fac2 % MOD + dp[i - 1][2] * fac2 % MOD) % MOD; dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; dp[i][2] = (dp[i - 1][0] + dp[i - 1][2]) % MOD; } printf("%lld\n", (dp[n][0] + dp[n][1] + MOD) % MOD); } return 0;}

转载于:https://www.cnblogs.com/KirinSB/p/9614801.html

你可能感兴趣的文章