ACM-ICPC 2018 徐州赛区网络预赛 A Hard to prepare
ACM-ICPC 2018 徐州赛区网络预赛 A Hard to prepare
https://nanti.jisuanke.com/t/31453
题目大意：
有n个人坐成一圈，然后有$2^k$种颜色可以分发给每个人，每个人可以收到相同的颜色，但是相邻两个人的颜色标号同或不能等于0，问分配方案数
注：以下所有的相同是指两个数同或为0
思路
- 通过观察得出在0～$2^k-1$的范围内对于每个数，与之同或为零的数是唯一的
- 首先举例尝试观察性质，假设第一个位置随便填，即有$2^k$种不同的填法，然后考虑第二个位置和第一个位置不同的填法有$2^k-1$种，然后考虑第三个位置和第二个位置不同的填法有$2^k-1$种。。。。。一直考虑到第n个位置和第n-1个位置，得出前n个位置只考虑每个位置和前一个位置不同的方案数有$2^k*(2^k-1)^{n-1}$
- 但是并没有考虑第n个数和第一个数相同的情况，这种情况是包含在第一种情况里面的，需要把这些从前一种情况中减去，第一位依旧是$2^k$，那么第n位便确定了，所有还剩下n-2位没有确定，保证他们和前面一位不相同，那么方案数是$2^k*(2^k-1)^{n-2}$，
- 但是我们并没有考虑第n-1个数和第n个数相同的情况，这种情况并不包含在第一种情况里面，但是在第二种情况的时候却把它减掉了，因此需要加回来，可见需要容斥
- 容斥
- 后一个状态 是 包含在前一个状态中的那些不合法状态
细节
- 考虑一种情况，但n为偶数的时候，考虑到最后一步的时候会出现abab这种情况，这种情况是计算，第二位和第三位相同的情况下，前两位和前面的数不相同的情况，但是第一位和第二位明显是相同的，所以这种情况，在一开始就没有被加进去，但是在最后一步却被减去了，所以在最后要加回这种情况
- ~(a^b)是不能实现同或的效果的，应该这么实现
- a^b==2^k-1
#include<bits/stdc++.h>
#define P 1000000007
#define ll long long
using namespace std;
int T,n,k,i;
ll m,ans;
ll pw(ll bs,ll x){
ll ans=1;while(x>0){if(x&1){ans=ans*bs%P;}bs=bs*bs%P;x>>=1;}
return ans;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
m=(pw(2,k)-1+P)%P;
ans=0;
for(i=0;i<n;i++){
if(i&1){
ans-=pw(m,n-1-i);
ans=(ans+P)%P;
}
else{
ans+=pw(m,n-1-i);
ans%=P;
}
}
if((n&1)==0)ans=(ans+1)%P;
ans=ans*pw(2,k)%P;
printf("%lld\n",ans);
}
}
版权声明：本文为VIrtu0s0原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。