题意:有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<queue>
#include<cstring>
#include<set>
#include<map>
#include<stack>
#include<string>
#include<cmath>
#include<vector>
#include<cstdio>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int maxn = 1e6 + ;
const int seed = ;
const ll MOD = 1e9 + ;
const int INF = 0x3f3f3f3f;
ll pmul(ll a, ll b){
ll ans = ;
while(b){
if(b & ) ans = ans * a % MOD;
a = a * a % MOD;
b >>= ;
}
return ans;
}
ll dp[maxn][]; //头尾无关 头尾相等 头尾值为0
int main(){
int T;
ll n, ans, k, fac, fac1, fac2, fac3;
scanf("%d", &T);
while(T--){
scanf("%lld%lld", &n, &k);
fac = pmul(, k);
fac1 = (fac - + MOD) % MOD;
fac2 = (fac - + MOD) % MOD;
fac3 = (fac - + MOD) % MOD;
dp[][] = fac;
dp[][] = ;
dp[][] = fac * (fac - + MOD) % MOD;
dp[][] = fac;
dp[][] = fac;
for(int i = ; i <= n; i++){
dp[i][] = (dp[i - ][] * fac3 % MOD + dp[i - ][] * fac2 % MOD + dp[i - ][] * fac2 % MOD) % MOD;
dp[i][] = (dp[i - ][] + dp[i - ][]) % MOD;
dp[i][] = (dp[i - ][] + dp[i - ][]) % MOD;
}
printf("%lld\n", (dp[n][] + dp[n][] + MOD) % MOD);
}
return ;
}
ACM-ICPC 2018 徐州赛区网络预赛A Hard to prepare(DP)题解的更多相关文章
-
ACM-ICPC 2018 徐州赛区网络预赛 A Hard to prepare(递推)
https://nanti.jisuanke.com/t/31453 题目 有n个格子拉成一个环,给你k,你能使用任意个数的0 ~ 2^k - 1,规定操作 i XNOR j 为~(i ^ j), ...
-
ACM-ICPC 2018 徐州赛区网络预赛 A Hard to prepare
https://nanti.jisuanke.com/t/31453 题目大意: 有n个人坐成一圈,然后有\(2^k\)种颜色可以分发给每个人,每个人可以收到相同的颜色,但是相邻两个人的颜色标号同或不 ...
-
ACM-ICPC 2018 徐州赛区网络预赛 A.Hard to prepare 【规律递推】
任意门:https://nanti.jisuanke.com/t/31453 A.Hard to prepare After Incident, a feast is usually held in ...
-
ACM-ICPC 2018 徐州赛区网络预赛 A. Hard to prepare (组合数学,递归)
A. Hard to prepare After Incident, a feast is usually held in Hakurei Shrine. This time Reimu asked ...
-
ACM-ICPC 2018 徐州赛区网络预赛(8/11)
ACM-ICPC 2018 徐州赛区网络预赛 A.Hard to prepare 枚举第一个选的,接下来的那个不能取前一个的取反 \(DP[i][0]\)表示选和第一个相同的 \(DP[i][1]\) ...
-
ACM-ICPC 2018 徐州赛区网络预赛 G. Trace (思维,贪心)
ACM-ICPC 2018 徐州赛区网络预赛 G. Trace (思维,贪心) Trace 问答问题反馈 只看题面 35.78% 1000ms 262144K There's a beach in t ...
-
ACM-ICPC 2018 徐州赛区网络预赛 J. Maze Designer (最大生成树+LCA求节点距离)
ACM-ICPC 2018 徐州赛区网络预赛 J. Maze Designer J. Maze Designer After the long vacation, the maze designer ...
-
计蒜客 1460.Ryuji doesn&#39;t want to study-树状数组 or 线段树 (ACM-ICPC 2018 徐州赛区网络预赛 H)
H.Ryuji doesn't want to study 27.34% 1000ms 262144K Ryuji is not a good student, and he doesn't wa ...
-
ACM-ICPC 2018 徐州赛区网络预赛 B(dp || 博弈(未完成)
传送门 题面: In a world where ordinary people cannot reach, a boy named "Koutarou" and a girl n ...
随机推荐
-
【转载】FaceBook - How to add a Privacy Policy to your Apps?
When you read through the Facebook Platform Policies, you'll notice that every Facebook App that sto ...
-
C-Sharp网络编程案例解析(Socket类的使用)
Server端: using System; using System.Collections.Generic; using System.Text; using System.Net; using ...
-
记一次网络原因导致的mysql连接中断问题(druid)
date: 2018-04-19 21:00 tag: java,mysql,exception,mat,调试,jvm 工具: gceasy.io, MAT 线上系统出现一个诡异的bug,通过heap ...
-
C语言数据结构基础学习笔记——静态查找表
查找:在数据集合中寻找满足某种条件的数据元素的过程称为查找. 查找表:用于查找的数据集合称为查找表,一般有以下操作:①查找是否在表中:②查找属性:③进行操作. 查找表又分为: ①静态查找表:只可以进行 ...
- js总结:onClick=“return confirm()”实现确认以及取消表单的提交
-
win7 下安装使用 nginx 出现500错误
配置虚拟主机域名后访问网站出现500错误,发现是因为路径的反斜杠问题,改成正斜杠后问题解决.
-
Python之shutil模块
shutil 高级的 文件,文件夹,压缩包 处理模块 正常把一个文件的内容拷贝到另外一个文件 s = file("test.py")d = file("test_copy ...
-
转:Linux实时将所有输出重定向到文件
转自: Linux的重定向机制十分好用,我们经常需要在服务器上挂起一个服务程序,然后将该程序的所有输出重定向到某个文件,这样即使我们注销了用户,程序依然在linux服务器上运行着. 但是重定向的输出经 ...
-
GIF图片合集(用于网络请求图片用)
GIF图片合集(用于网络请求图片用)
-
编写每天定时切割Nginx日志的脚本
自动每天定时切割Nginx日志的脚本,很方便很好用,推荐给大家使用.本脚本也是参考了张宴老师的文章,再次感谢张宴老师.1.创建脚本/usr/local/nginx/sbin/cut_nginx_log ...