Codeforces Round #631 (Div. 2) - Thanks, Denis aramis Shitov! D. Dreamoon Likes Sequences（位运算+数学）

题目链接


思路：能满足条件的a数组一定满足a【i-1】<a【i】并且a【i-1】的最高位要小于a【i】的最高位，例如a【i-1】为10的话，a【i】可以为100、1000、10000.。。。（以上以下都用二进制表示），由于n的长度不限定，我们就先找到2的幂次方中与d靠最近的（也就是代码里的pos），我们就可以考虑以下每一位的贡献，对于第i位a【i】有几种选择，假设a【i】是要从100和1000里来选择，那么很显然a【i】一共有1000个数可以选择（注意这个1000是二进制），其他位依次类推，2的幂次可以打表，最后根据乘法原理再相乘。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int f[maxn];
int main()
{int T,pos;f[0]=1;for(int i=1;i<=31;++i) f[i]=f[i-1]*2;scanf("%d",&T);while(T--){ll d,mod,ans=1;scanf("%lld %lld",&d,&mod);for(pos=0;d>=f[pos];pos++);ll t=d-f[pos-1]+1;for(int i=0;i<=pos-2;++i) ans=(ans+ans*f[i])%mod;ans=(ans+t*ans)%mod;printf("%lld\n",(ans-1+mod)%mod);}
}