https://nanti.jisuanke.com/t/31453
题目大意:
有 n 个人坐成一圈, 然后有 $$2k$$ 种颜色可以分发给每个人, 每个人可以收到相同的颜色, 但是相邻两个人的颜色标号同或不能等于 0, 问分配方案数
注: 以下所有的相同是指两个数同或为 0
思路
通过观察得出在 0~$$2k1$$ 的范围内对于每个数, 与之同或为 0 的数是唯一的
首先举例尝试观察性质, 假设第一个位置随便填, 即有 $$2k$$ 种不同的填法, 然后考虑第二个位置和第一个位置不同的填法有 $$2k1$$ 种, 然后考虑第三个位置和第二个位置不同的填法有 $$2k1$$ 种..... 一直考虑到第 n 个位置和第 n1 个位置, 得出前 n 个位置只考虑每个位置和前一个位置不同的方案数有 $$2k*(2k1){n1}$$
但是并没有考虑第 n 个数和第一个数相同的情况, 这种情况是包含在第一种情况里面的, 需要把这些从前一种情况中减去, 第一位依旧是 $$2k$$, 那么第 n 位便确定了, 所有还剩下 n2 位没有确定, 保证他们和前面一位不相同, 那么方案数是 $$2k*(2k1){n2}$$,
但是我们并没有考虑第 n1 个数和第 n 个数相同的情况, 这种情况并不包含在第一种情况里面, 但是在第二种情况的时候却把它减掉了, 因此需要加回来, 可见需要容斥
容斥
后一个状态 是 包含在前一个状态中的那些不合法状态
细节
考虑一种情况, 但 n 为偶数的时候, 考虑到最后一步的时候会出现 abab 这种情况, 这种情况是计算, 第二位和第三位相同的情况下, 前两位和前面的数不相同的情况, 但是第一位和第二位明显是相同的, 所以这种情况, 在一开始就没有被加进去, 但是在最后一步却被减去了, 所以在最后要加回这种情况
~(ab) 是不能实现同或的效果的, 应该这么实现
- ab==2k1
- #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,n1i);
- ans=(ans+P)%P;
- }
- else{
- ans+=pw(m,n1i);
- ans%=P;
- }
- }
- if((n&1)==0)ans=(ans+1)%P;
- ans=ans*pw(2,k)%P;
- printf("%lld\n",ans);
- }
- }
来源: https://www.cnblogs.com/VIrtu0s0/p/9619121.html