結果
問題 | No.569 3 x N グリッドのパスの数 |
ユーザー | 👑 horiesiniti |
提出日時 | 2017-09-14 18:15:41 |
言語 | Ruby (3.3.0) |
結果 |
AC
|
実行時間 | 588 ms / 2,000 ms |
コード長 | 2,211 bytes |
コンパイル時間 | 142 ms |
コンパイル使用メモリ | 7,296 KB |
実行使用メモリ | 12,800 KB |
最終ジャッジ日時 | 2024-04-25 09:21:00 |
合計ジャッジ時間 | 24,006 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 98 ms
12,032 KB |
testcase_01 | AC | 97 ms
12,288 KB |
testcase_02 | AC | 109 ms
12,288 KB |
testcase_03 | AC | 111 ms
12,416 KB |
testcase_04 | AC | 115 ms
12,288 KB |
testcase_05 | AC | 120 ms
12,416 KB |
testcase_06 | AC | 120 ms
12,288 KB |
testcase_07 | AC | 119 ms
12,544 KB |
testcase_08 | AC | 123 ms
12,416 KB |
testcase_09 | AC | 123 ms
12,416 KB |
testcase_10 | AC | 127 ms
12,544 KB |
testcase_11 | AC | 123 ms
12,416 KB |
testcase_12 | AC | 122 ms
12,416 KB |
testcase_13 | AC | 123 ms
12,416 KB |
testcase_14 | AC | 122 ms
12,416 KB |
testcase_15 | AC | 128 ms
12,544 KB |
testcase_16 | AC | 132 ms
12,672 KB |
testcase_17 | AC | 135 ms
12,544 KB |
testcase_18 | AC | 131 ms
12,416 KB |
testcase_19 | AC | 135 ms
12,672 KB |
testcase_20 | AC | 328 ms
12,672 KB |
testcase_21 | AC | 330 ms
12,672 KB |
testcase_22 | AC | 328 ms
12,800 KB |
testcase_23 | AC | 329 ms
12,672 KB |
testcase_24 | AC | 331 ms
12,672 KB |
testcase_25 | AC | 327 ms
12,800 KB |
testcase_26 | AC | 327 ms
12,672 KB |
testcase_27 | AC | 328 ms
12,672 KB |
testcase_28 | AC | 325 ms
12,672 KB |
testcase_29 | AC | 325 ms
12,800 KB |
testcase_30 | AC | 327 ms
12,672 KB |
testcase_31 | AC | 328 ms
12,800 KB |
testcase_32 | AC | 328 ms
12,800 KB |
testcase_33 | AC | 332 ms
12,800 KB |
testcase_34 | AC | 355 ms
12,672 KB |
testcase_35 | AC | 349 ms
12,800 KB |
testcase_36 | AC | 346 ms
12,672 KB |
testcase_37 | AC | 347 ms
12,672 KB |
testcase_38 | AC | 347 ms
12,800 KB |
testcase_39 | AC | 345 ms
12,800 KB |
testcase_40 | AC | 568 ms
12,800 KB |
testcase_41 | AC | 578 ms
12,672 KB |
testcase_42 | AC | 576 ms
12,800 KB |
testcase_43 | AC | 569 ms
12,800 KB |
testcase_44 | AC | 577 ms
12,672 KB |
testcase_45 | AC | 571 ms
12,672 KB |
testcase_46 | AC | 588 ms
12,672 KB |
testcase_47 | AC | 570 ms
12,800 KB |
testcase_48 | AC | 571 ms
12,672 KB |
testcase_49 | AC | 571 ms
12,800 KB |
testcase_50 | AC | 567 ms
12,672 KB |
testcase_51 | AC | 573 ms
12,672 KB |
testcase_52 | AC | 574 ms
12,672 KB |
testcase_53 | AC | 573 ms
12,672 KB |
testcase_54 | AC | 574 ms
12,672 KB |
testcase_55 | AC | 571 ms
12,800 KB |
testcase_56 | AC | 573 ms
12,672 KB |
testcase_57 | AC | 574 ms
12,672 KB |
testcase_58 | AC | 580 ms
12,800 KB |
testcase_59 | AC | 577 ms
12,672 KB |
コンパイルメッセージ
Syntax OK
ソースコード
require 'set' mod1=1000000007 def f(a1,a2) a1.each{|e| a2.push([e[0].reverse(),e[1].reverse]) } end def g(all,es) es.each{|e1| e1.each{|e2| all.push([e2[0],e2[1],1]) } } end def f2(perm,perm2) res=[] sum=[] mod1=1000000007 perm.each{|e1| left=e1[0] r1=e1[1] p1=e1[2] perm2.each{|e2| l1=e2[0] right=e2[1] p2=e2[2] if r1==l1 then p3=(p1*p2)%mod1 sum.push([left,right,p3]) end } } sum.sort! e1=sum[0] sum.shift sum.each{|e2| if e1[0]==e2[0] && e1[1]==e2[1] then e1[2]=(e1[2]+e2[2])%mod1 else res.push([e1[0],e1[1],e1[2]]) e1=e2 end } res.push([e1[0],e1[1],e1[2]]) return res end all=[] a111=[ ["0001","1000"], ["1000","0001"]] a110=[ ["1000","0010"], ["1023","0001"], ["0010","1000"], ["0001","3021"]] a011=[] f(a110,a011) a101=[ ["1230","0001"], ["1203","0010"], ["1000","0123"], ["0100","1023"], ["3021","0100"], ["0321","1000"], ["0001","3210"], ["0010","3201"]] a100=[ ["0123","1023"], ["0100","1000"], ["0321","3021"], ["3021","0321"], ["1000","0100"], ["1023","0123"], ["0010","3210"], ["0001","3201"], ["1230","0010"], ["1203","0001"]] a001=[] f(a100,a001) a010=[ ["0010","0100"], ["0100","0010"], ["3201","3021"], ["1203","1023"], ["1023","1203"], ["3021","3201"], ["0123","0001"], ["0001","0321"], ["1000","1230"], ["3210","1000"]] a000=[ ["1000","1000"], ["0100","0100"], ["0010","0010"], ["0001","0001"], ["1230","1230"], ["1203","1203"], ["1023","1023"], ["0123","0123"], ["0321","0321"], ["3201","3201"], ["3021","3021"], ["3210","3210"]] g(all,[a000,a001,a010,a100,a011,a101,a110,a111]) s=[ ["0000","1000",1], ["0000","0100",1], ["0000","0010",1], ["0000","0001",1], ["0000","1230",1], ["0000","1203",1], ["0000","1023",1], ["0000","0123",1]] g=[ ["0001","0000",1], ["0010","0000",1], ["0100","0000",1], ["1000","0000",1], ["1203","0000",1], ["1230","0000",1], ["1023","0000",1], ["0123","0000",1] ] n=gets.to_i n=n-1 perm2=[] allPerm=[] s.each{|e| allPerm.push([e[0],e[1],1]) } all.each{|e| perm2.push([e[0],e[1],1]) } while n>0 if n%2==1 then allPerm=f2(allPerm,perm2) end perm2=f2(perm2,perm2) n=n/2 end ans=f2(allPerm,g) puts ans[0][2]%mod1