(计蒜客 31453)ACM-ICPC 2018 徐州赛区网络预赛 - A. Hard to prepare - (计数递归)

本文主要是介绍(计蒜客 31453)ACM-ICPC 2018 徐州赛区网络预赛 - A. Hard to prepare - (计数递归),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:https://nanti.jisuanke.com/t/31453

题解参考自:https://blog.csdn.net/Jaihk662/article/details/82561427

题意:n个数字排成一圈,每个数字范围[0, \small 2^k-1],问有多少种不同的序列满足对于所有相邻的两个数字,它们异或值不能为\small 2^k-1,其中第一个数字和最后一个数字也算相邻。(0<n,k≤1e6) .

解析:①.首先易知第1个数字有2^k种选择,第2到第n-1个数字均有2^k-1种选择(保证与前一个异或值不能为0即可),而第n个数字即不可以和第1个数冲突,又不能和第n-1个数冲突。那么此时的总方案数为:\small 2^k(2^k-2)(2^k-1)^{n-2}

          ②.但是发现当第1个数与第n-1个数相同时,由于第n个数字少了一个冲突所以它有2^k-1种选择,所以上面对第n个数字少统计了一种情况,此情况方案就是当把第1个数与第n-1个数合并成一个后的长度为n-2的序列的总方案数。

代码:

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

 

 

这篇关于(计蒜客 31453)ACM-ICPC 2018 徐州赛区网络预赛 - A. Hard to prepare - (计数递归)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/359597

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

ASIO网络调试助手之一:简介

多年前,写过几篇《Boost.Asio C++网络编程》的学习文章,一直没机会实践。最近项目中用到了Asio,于是抽空写了个网络调试助手。 开发环境: Win10 Qt5.12.6 + Asio(standalone) + spdlog 支持协议: UDP + TCP Client + TCP Server 独立的Asio(http://www.think-async.com)只包含了头文件,不依

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码

poj 3181 网络流,建图。

题意: 农夫约翰为他的牛准备了F种食物和D种饮料。 每头牛都有各自喜欢的食物和饮料,而每种食物和饮料都只能分配给一头牛。 问最多能有多少头牛可以同时得到喜欢的食物和饮料。 解析: 由于要同时得到喜欢的食物和饮料,所以网络流建图的时候要把牛拆点了。 如下建图: s -> 食物 -> 牛1 -> 牛2 -> 饮料 -> t 所以分配一下点: s  =  0, 牛1= 1~

poj 3068 有流量限制的最小费用网络流

题意: m条有向边连接了n个仓库,每条边都有一定费用。 将两种危险品从0运到n-1,除了起点和终点外,危险品不能放在一起,也不能走相同的路径。 求最小的费用是多少。 解析: 抽象出一个源点s一个汇点t,源点与0相连,费用为0,容量为2。 汇点与n - 1相连,费用为0,容量为2。 每条边之间也相连,费用为每条边的费用,容量为1。 建图完毕之后,求一条流量为2的最小费用流就行了

poj 2112 网络流+二分

题意: k台挤奶机,c头牛,每台挤奶机可以挤m头牛。 现在给出每只牛到挤奶机的距离矩阵,求最小化牛的最大路程。 解析: 最大值最小化,最小值最大化,用二分来做。 先求出两点之间的最短距离。 然后二分匹配牛到挤奶机的最大路程,匹配中的判断是在这个最大路程下,是否牛的数量达到c只。 如何求牛的数量呢,用网络流来做。 从源点到牛引一条容量为1的边,然后挤奶机到汇点引一条容量为m的边

计蒜客 Skiing 最长路

In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski resort has MM different ski paths and NN different flags situated at those turning points. The ii-th path from the

计蒜客 Half-consecutive Numbers 暴力打表找规律

The numbers 11, 33, 66, 1010, 1515, 2121, 2828, 3636, 4545 and t_i=\frac{1}{2}i(i+1)t​i​​=​2​​1​​i(i+1), are called half-consecutive. For given NN, find the smallest rr which is no smaller than NN

配置InfiniBand (IB) 和 RDMA over Converged Ethernet (RoCE) 网络

配置InfiniBand (IB) 和 RDMA over Converged Ethernet (RoCE) 网络 服务器端配置 在服务器端,你需要确保安装了必要的驱动程序和软件包,并且正确配置了网络接口。 安装 OFED 首先,安装 Open Fabrics Enterprise Distribution (OFED),它包含了 InfiniBand 所需的驱动程序和库。 sudo