ACM-ICPC 2018 徐州赛区网络预赛 A Hard to prepare(递推)

https://nanti.jisuanke.com/t/31453

题目

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

分析

因为都是无符号了，那么题目就是要求相邻的数同或的结果不为0，即异或的结果不为2^k-1。

第1个数有 $small 2^k$ 种选择，第2个数到第n-1个数都有 $small 2^k-1$ 种选择，第n个数有 $small 2^k-2$ 种选择

所以答案就是 $small 2^k(2^k-2)(2^k-1)^{n-2}$

可是当第1个数和第n-1个数相同时，第n个数有 $small 2^k-1$ 种选择，与上面相比，少了一种选择。于是此时将第1个数和第n-1个数合并起来，这样长度就变成n-2了，因为当它们相同时，第n个数多了一种选择，也是唯一一种。然后递归求解。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
LL Pow(LL a, LL b){
    LL ans = 1;
    while(b){
        if(b%2)    ans = ans*a%mod;
        a = a*a%mod;
        b /= 2;
    }
    return ans;
}
LL er[maxn], ans[maxn];
LL solve(int n, int m){
    if(n==2) return er[m]*(er[m]-1)%mod;
    if(n==1) return er[m];
    return (er[m]*Pow(er[m]-1, n-2)%mod*max(er[m]-2, 0ll)%mod+solve(n-2, m))%mod;
}
int main(){
    int T, n, m;
    er[0]=1;
    for(int i=1;i<=maxn;i++) er[i] = er[i-1]*2%mod;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        printf("%lld
", solve(n, m));
    }
    return 0;
}