ACM-ICPC 2018 徐州赛区网络预赛 A.Hard to prepare 【规律递推】

约定不等于承诺〃 2024-04-17 18:24 72阅读 0赞

t题意：就是有n个人围成圈，每个人能选择![2^\{k\}][2_k]顶不同的帽子，但是相邻两个人选择的帽子的编号不能同或为0，问有多少种方案

联想 + 推理

我们假设有  颗珠子，   我们不考虑开头 对末尾的限制， 只是考虑  对 的限制，答案就是 ， 这些情况是多了的，多了   这种情况， 然后我们再来计算这种情况有多少？

现在的条件 是 已知 第一个是 ， 最后一个是， 问一共有多少种方案。

我们先考虑简单的情况 ，假设一共只有 3个 珠子  ，我们第一个是A，第三个是， 那么第二个只能选 个。 所以多了的就是 中情况。

然后推广一下， 我们考虑   这个位置是 ，那么   这个位置 只有    种情况， 所以我们减掉  种情况，可是这个情况仍然 少了   这个位置上 是 的情况，所以我们还得加上 现在确定 第一个位置是  A ，第  个位置是  的情况， 所以一直 .......   , 结束的位置在哪里呢？

结束的位置也就是 最早出现 的位置，也就是  第三个位置，所以 我们可以变得位置计算到 第二个也就是  可以了

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int mod=1e9+7;
    ll pow_mod(ll base,ll n,int mod){
        ll ans=1;
        while(n){
            if(n&1)ans=ans*base%mod;
            base=base*base%mod;
            n>>=1;
        }
        return ans%mod;
    }
    int main(){
        int T;scanf("%d",&T);
        while(T--){
            ll n,k;
            scanf("%lld %lld",&n,&k);
            ll ans=0,t1=pow_mod(2,k,mod);
            ll t2=(t1-1+mod)%mod,t3=(t1-2+mod)%mod;
            ll sum=t1;
            for(int i=2;i<=n;i++)sum=sum*t2%mod;
            ans=sum;
            ll inv_t2=pow_mod(t2,mod-2,mod);
            for(int i=n-1;i;i--){
                sum=sum*inv_t2%mod;
                if((n-i)%2==0) ans=(ans-sum*t3%mod+mod)%mod;
            }
            printf("%ll\n",ans);
        }
        return 0;
    }

大佬代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    #define rep(i,a,b) for(int i=a;i<b;++i)
    #define per(i,a,b) for(int i=b-1;i>=a;--i)
    const int mod=1e9+7;
     
    LL pow_mod(LL base,LL n,int mod) {
    	LL ans=1;
    	while(n) {
    		if(n&1)ans=ans*base%mod;
    		base=base*base%mod;
    		n>>=1;
    	}
    	return ans%mod;
    }
     
    int main() {
    	int T;
    	scanf("%d",&T);
    	while(T--) {
    		LL N,K;
    		scanf("%lld %lld",&N,&K);
    		LL ans=0;
    		LL t1=pow_mod(2,K,mod);
    		LL t2=(t1-1+mod)%mod;
    		LL t3=(t1-2+mod)%mod;
     
    		LL sum=t1;
    		for(int i=2; i<=N; i++)sum=sum*t2%mod;
    		ans=sum;
     
    		LL inv_t2=pow_mod(t2,mod-2,mod);
    		//LL inv_
    		//	printf("ans:%lld\n",ans);
    		for(int i=N-1; i>=1; --i) {
    			sum=sum*inv_t2%mod;
    			if((N-i)%2==0) {
    				LL tmp=sum*t3%mod;
    				ans=(ans-tmp+mod)%mod;
    				//	printf("i:%d ans:%lld sum:%lld tmp:%lld\n",i,ans,sum,tmp);
    			}
    		}
    		printf("%lld\n",ans);
    	}
    	return 0;
    }

[2_k]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9wcml2YXRlLmNvZGVjb2dzLmNvbS9naWYubGF0ZXg_MiU1RSU3QmslN0Q?x-oss-process=image/format,png