CodeForces - 1330D Dreamoon Likes Sequences(组合数学)

题目链接：点击查看

题目大意：给出一个限制 d 与模数 mod ，求出可以构造出的满足条件的数组 a 的个数，需要满足以下条件：

数组 a 的长度大于等于 1 

数组 a 严格递增

数组 a 的最小值大于等于 1 ，数组 a 的最大值小于等于 d

对于数组 a ，构造出一个数组 b ：

i == 1 时：b[ 1 ] = a[ 1 ]

i > 1 时：b[ i ] = b[ i - 1 ] ^ a[ i ] 

数组 b 严格递增

题目分析：1900分的组合数学问题，直接扔给队友去做了，赛后补题好歹算是学会了，数学渣真的没办法呀

通过观察或者适当猜测，可以看出这个问题是一个基于位运算的题目，换句话说，如果在数组 a 中选择了 2 ，接下来就没法选择 3，如果选择了 4 ，接下来就没办法选择 5 6 7，选择了 8 ，接下来就没法选择 9 10 11 12 13 14 15 ，也就是说对于 a[ i ] 的每个数字而言，其二进制中最高位的那个 1 的位置一定是唯一的，且是递增的

有了这个结论之后就不难实现了，对于每个二进制的 i 来说，我们可以选择的数字有种，需要注意的是我们还需要加入一种情况，那就是第 i 个位置不选择数字的情况，也就是对于每个 i 的方案数变成了种情况了，累乘一下就行了，最后需要减去一，这个一代表的是所有位置都不选的情况，然后注意特判一下 n 就好了

代码：
 

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n,mod;scanf("%d%d",&n,&mod);LL ans=1;for(int i=0;i<30;i++){if((1<<i)>n)break;ans=(ans*(min((1<<(i+1))-1,n)-(1<<i)+2))%mod;}ans=(ans+mod-1)%mod;printf("%lld\n",ans);}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1330D Dreamoon Likes Sequences(组合数学)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。