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个数有ACM-ICPC 2018 徐州赛区网络预赛 A Hard to prepare(递推)种选择,第2个数到第n-1个数都有ACM-ICPC 2018 徐州赛区网络预赛 A Hard to prepare(递推)种选择,第n个数有ACM-ICPC 2018 徐州赛区网络预赛 A Hard to prepare(递推)种选择

所以答案就是ACM-ICPC 2018 徐州赛区网络预赛 A Hard to prepare(递推)

可是当第1个数和第n-1个数相同时,第n个数有ACM-ICPC 2018 徐州赛区网络预赛 A Hard to prepare(递推)种选择,与上面相比,少了一种选择。于是此时将第1个数和第n-1个数合并起来,这样长度就变成n-2了,因为当它们相同时,第n个数多了一种选择,也是唯一一种。然后递归求解。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 1e9 + ;
const int maxn = 1e6 + ;
LL Pow(LL a, LL b){
LL ans = ;
while(b){
if(b%) ans = ans*a%mod;
a = a*a%mod;
b /= ;
}
return ans;
}
LL er[maxn], ans[maxn];
LL solve(int n, int m){
if(n==) return er[m]*(er[m]-)%mod;
if(n==) return er[m];
return (er[m]*Pow(er[m]-, n-)%mod*max(er[m]-, 0ll)%mod+solve(n-, m))%mod;
}
int main(){
int T, n, m;
er[]=;
for(int i=;i<=maxn;i++) er[i] = er[i-]*%mod;
scanf("%d", &T);
while(T--){
scanf("%d%d", &n, &m);
printf("%lld\n", solve(n, m));
}
return ;
}
上一篇:vue中的axios.post使用json数据传输,出现请求头字段内容类型是不被允许的情况的解决方案


下一篇:centos7下安装vnc更改vnc默认端口号