結果

問題 No.420 mod2漸化式
ユーザー aka_satana_ha
提出日時 2017-11-27 16:48:57
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 32 ms / 1,000 ms
コード長 868 bytes
コンパイル時間 125 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-11-27 11:01:36
合計ジャッジ時間 2,166 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)

#よくわからないケースの間引き
if x==0:
    print("1","0")
    exit()
if x>31:
    print("0","0")
    exit()

#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