<span>Codeforces Round #631 (Div. 2) D.Dreamoon Likes Sequences</span>

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 
 5 ll dp[100];
 6 ll b[100];
 7 
 8 int main()
 9 {
10     ll t;
11     cin>>t;
12     while(t -- ){
13         memset(b,0,sizeof(b));
14         memset(dp,0,sizeof(dp));
15         ll d,m;
16         cin>>d>>m;
17         ll x = d;
18         ll s = 1,k = 1;
19         while(x){
20             b[k ++ ] = min(s,d - s + 1);  //第k个数的取法
21             //s是当前位可以取的个数，d-s+1是最大到d还可以取的个数
22             x >>= 1;
23             s <<= 1;
24         }
25         for (ll  i= 1;  i< k; ++i )
26             dp[i] = (dp[i - 1]%m + b[i] % m + dp[i - 1] * b[i] % m) % m;  //只有i-1位+只有最后一位+（i-1位的个数）*（第i位个数）
27         cout<<dp[k-1]<<endl;
28     }
29     return 0;
30 }