L - Less Coin Tosses Gym - 102346L
題目鏈接
演算法
打表+找規律
時間復雜度O(logN)
1.題意說的是給定你n位的二進制串，除了成對的（就是指那些1的個數相同或0的個數相同的），那些不成對的數有幾個，比如n為3時，可以有000,001,010,011,100,101,110,111這八種二進制數，其中001可以與010配對，011可以與110配對，剩余的無法再配對，所以最后輸出4，
2.看要求的數的范圍2<=N<=10^18，非常大，所以說不可能暴力去做，一定存在某種規律，
3.既然成對的就是指二進制串中1的個數相同，那么我們可以用組合數的知識來解決，即從n位數中挑m位為1，看這樣的數有幾個，若為偶數，則說明沒有不成對的，否則說明有落單的，這時加1即可，總結得出下列公式：
\[\displaystyle \sum_{i=0}^n (C_{n}^{i}\%2) \]4.公式有了，問題來了，n這么大怎么算，對于這種題，很大可能性說明存在某種規律，如何找到規律，就需要打表實作，可以根據下列代碼來打表，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
/*打表*/
const int N = 1000;
ll c[N][N];
int n;
ll res[N];
void init()
{
for(int i = 0; i < N;i ++)
for(int j = 0; j <= i; j++)
{
if(!j) c[i][j] = 1;
else
c[i][j] = (c[i-1][j] + c[i-1][j-1]);
}
}
int main()
{
init();
for(int i = 2; i < N; i++)
{
for(int j = 0; j <= i; j++)
{
res[i] += (c[i][j] % 2);
}
cout << "res[" << i << "] = " << res[i] << endl;
}
}
由于沒有取余導致后面的數溢位變成負數了，不過沒有關系，我們只需要看前面幾個數就能找到規律，
看上面這張圖，仔細觀察顏色相同的下劃線標注的位置，好像成2的倍數的數他們的結果相同，好像還有點什么，那么我們就把每個數拆分成二進制數，找到他們在輸出中的位置，仔細觀察，
將上圖中二進制數對應的結果進行比對，再與二進制數本身的特征加以比較，發現最終的結果與n對應的二進制數中的1的個數有關，由此，得出了最終規律，
5.總結一下，規律為n對應的二進制數中1的個數k，答案為2^k，
C++代碼
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
/*打表
const int N = 1000;
ll c[N][N];
int n;
ll res[N];
void init()
{
for(int i = 0; i < N;i ++)
for(int j = 0; j <= i; j++)
{
if(!j) c[i][j] = 1;
else
c[i][j] = (c[i-1][j] + c[i-1][j-1]);
}
}
int main()
{
init();
for(int i = 2; i < N; i++)
{
for(int j = 0; j <= i; j++)
{
res[i] += (c[i][j] % 2);
}
cout << "res[" << i << "] = " << res[i] << endl;
}
}
*/
ll n;
int main()
{
cin >> n;
ll res = 1;
while(n)
{
if(n & 1) res <<= 1;
n >>= 1;
}
cout << res ;
return 0;
}
代碼中求組合數的模板來源于yxc大佬的數學知識模板
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135492.html
標籤：其他
上一篇：合并兩個排序的鏈表