ACM-ICPC 2018 徐州赛区网络预赛A题
程序员文章站
2022-06-04 15:38:50
...
【题目】
【题意】
英语不好,如果翻译没差多少的话,出题人应该是个东方厨,也算是同道中人了。即有个编号的面具,面具的编号为。然后有N个人围成一圈,每个人都带个面具(面具编号可以重复),让相邻的两个人的面具编号值异或后取反不为0的方法有多少种。
【题解】
两个数异或取反后为0,即取反之前的数的二进制全都是由1组成,也就是两个数是互补的,而能与一个数互补的数只有一个,而我们需要避免这种情况。这就需要在两个数的中间插入数,把他们隔离开,而且因为是围成一个圈,所以第一个数和最后一个数也是相邻的,从而就能得到最普通情况的可能性总数为:,即第一个数可以取个数,中间的数不能跟第一个数互补的,所以可以取的数为个数,而第三个数不能跟中间的数互补,也不能跟第一个数互补,所以可以取个数。如果是这样计算的话,就会漏掉中间的最后一个数跟第一个数相等的情况,如果这个数跟第一个数一样的话,最后一个不能取的数就只会有一个,即。即可能性就变成,也就是说,我们会少一种情况。而这样的话,根据乘法原理,我们只需要之前的数加上当前中间最后一个数前面的那些数就行了,即。这也就能发现这道题,突然变成了一个递归题,因为,中间的数可能是会有很多个,而每次都会造成加上普通情况而少一种情况的情况,得一直累加到剩下的数为或者这两个可以确定数量的时候,才算真正的把可能性总和出来。
#include<iostream>
#include<cstring>
#include<sstream>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<list>
#include<set>
#include<map>
#include<algorithm>
#define fi first
#define se second
#define MP make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define lc (p<<1)
#define rc (p<<1|1)
#define MID (tree[p].l+tree[p].r)>>1
#define Sca(x) scanf("%d",&x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)
#define Scl2(x,y) scanf("%lld%lld",&x,&y)
#define Scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define Pri(x) printf("%d\n",x)
#define Prl(x) printf("%lld\n",x)
#define For(i,x,y) for(int i=x;i<=y;i++)
#define _For(i,x,y) for(int i=x;i>=y;i--)
#define FAST_IO std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define STOP system("pause")
#define ll long long
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const double Pi = acos(-1.0);
using namespace std;
template <class T>void tomax(T&a,T b){ a=max(a,b); }
template <class T>void tomin(T&a,T b){ a=min(a,b); }
const int N=1e6+5;
const int MOD=1e9+7;
ll f[N];
int qpow(ll a,int k){
ll ans=1;
while(k){
if(k&1) ans=(ans*a)%MOD;
a=(a*a)%MOD;
k>>=1;
}
return ans;
}
int dfs(int n,int k){
if(n==2)
return f[k]*(f[k]-1)%MOD;
if(n==1)
return f[k];
ll ans=((f[k]*qpow(f[k]-1,n-2)%MOD)*(f[k]-2)%MOD+dfs(n-2,k))%MOD;
return ans;
}
int main(){
f[0]=1;
For(i,1,N-5) f[i]=f[i-1]*2%MOD;
int T; Sca(T);
while(T--){
int n,k; Sca2(n,k);
Pri(dfs(n,k));
}
}
推荐阅读
-
【计蒜客】2018ICPC徐州赛区网络赛H Ryuji doesn't want to study(树状数组)
-
ACM-ICPC 2018 徐州赛区网络预赛 H - Ryuji doesn't want to study
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study(线段树区间求和)
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study—— 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 H Ryuji doesn't want to study(线段树 两种做法)
-
【ACM-ICPC 2018 徐州赛区网络预赛】H题 Features Track ---- 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 G. Trace (线段树维护)
-
2018 沈阳赛区网络预赛 F. Fantastic Graph 有上下界可行流
-
ACM-ICPC 2018 徐州赛区网络预赛 Trace
-
Trace-----ACM-ICPC 2018 徐州赛区网络预赛