結果

問題 No.420 mod2漸化式
コンテスト
ユーザー aka_satana_ha
提出日時 2017-11-27 16:43:19
言語 Python3
(3.15.0 + numpy 2.5.4 + scipy 1.18.1 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WA  
実行時間 -
コード長 744 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 57 ms
コンパイル使用メモリ 15,360 KB
実行使用メモリ 11,580 KB
最終ジャッジ日時 2026-09-30 19:35:12
合計ジャッジ時間 6,890 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 32 WA * 1 TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

x=int(input())

#nCr
def comb(n,r):
    mul_bunsi=1
    for i in range(n-r+1,n+1):
        mul_bunsi*=i
    mul_bunbo=1
    for i in range(1,r+1):
        mul_bunbo*=i
    return int(mul_bunsi/mul_bunbo)

#2進数での桁数を求める
digit=1
mul=1
while(1):
    mul=mul*2
    if mul>x:
        break
    digit+=1

#漸化式の出力は2進数における１の数となっているのでこれを集計する
n_num=0
#1になっている最上桁で場合分け
for i in range(1,32):
    if i<x:
        continue
    n_num+=comb(i-1,x-1)
#総和はすべてを足すと各桁が同じだけ出てくることを利用する
one_num=comb(30,x-1)
n_sum=0
radix=1
for i in range(1,32):
    n_sum+=radix*one_num
    radix*=2
print(n_num,n_sum)
0