ゆっくりでいいさ

被问到上次ZOJ Monthly中的H题Special Special Judge III怎么用容斥原理做。确实我只在解题报告中提了一句可以这么做，然后就丢下了一段python代码跑了。现在来详细解释一下如何运用容斥原理求一个Hyperrectangle被Hyperplane切割后剩余部分的体积。这里假定n维空间内的Hyperrectangle为

而对应的Hyperplane为

那么我们实际要求的就是Convex

的体积。

不妨先考虑两个二维平面上的例子：

SPOJ24. Small factorials[FCTRL2]就是阶乘计算加高精度运算。以下是用内置大数支持的perl, php, java, ruby, python, haskell, bash, scheme等语言实现的代码。

haskell

main = interact $ unlines . map (\i -> show $ f !! read i) . tail . words
	where f = scanl (*) 1 [1 ..]

perl

#!/usr/bin/perl -w

use strict;
use Math::BigInt lib => 'GMP';

my @f = ();
push @f, Math::BigInt->new(1);
for (my $i = 1; $i <= 100; ++$i) {
	push @f, $f[$#f]->copy()->bmul($i);
}
chomp(my $re = <STDIN>);
for (my $ri = 1; $ri <= $re; ++$ri) {
	chomp(my $n = <STDIN>);
	print "$f[$n]\n";
}

php

As I cannot find any appropriate haskell brushes for SyntaxHighlighter, I developed one by myself. You can download it here, I do hope it will be helpful. If you find any bugs or have any suggestions, please comment here or email me.

SyntaxHighlighter提供了大多流行语言的Brush，但是相对而言支持的语言还是比较少的。如果你需要的某种语言不幸不在支持列表内，那么你还可以求助于第三方Brush，这里有一个更加丰富语言列表，不过不是所有的语言都有对应的Brush。更不幸的是，我需要的Haskell语言甚至都不在这个列表里。google了一下还是看到有别人写的Brush，不过功能实在有点弱，所以我开始按照Handy Custom Brushes Development Guide自己写一个Haskell Brush。

在Guide的指导下，在参考着其他语言的Brush和其他平台下Haskell的高亮配置文件，我自己的shBrushHaskell.js也有模有样的完成了。最后要做的就是把它加到wordpress的plugin里，参照Adding A New Brush (Language)便能很容易完成。事实上在在我使用的SyntaxHighlighter Evolved里只要先把shBrushHaskell.js上传到合适的位置，比如$plugin_dir/watashi-no-brushes，再对syntaxhighlighter.php做两处修改就好了：

1. 在一堆wp_register_script中间插入一句

   /* register my brush */
   wp_register_script('syntaxhighlighter-brush-haskell', plugins_url('syntaxhighlighter/watashi-no-brushes/shBrushHaskell.js'), array('syntaxhighlighter-core'), '20091224'); // ADD_THIS_LINE
   

2. 再添加映射

   $this->brushes = (array) apply_filters( 'syntaxhighlighter_brushes', array(
       /* ... */
       'haskell' => 'haskell', // ADD_THIS_LINE
   ) );
   

大功告成。

首先拿A + B Problem做个测试：

main = do
    input <- getContents
    putStr $ unlines $ map show $ doEMP $ map read $ words input

doEMP [] = []
doEMP (a:b:o) = a + b : doEMP o

再加两个demo，第一个是ProjectEuler的41：