=== ===

=== ===

題解

沒錯(cuò)這本來應(yīng)該是ATP胡策第一次A題但是然而but被卡了hash然后就變成了暴力分。。這里貼的這個(gè)破代碼就是考試的時(shí)候?qū)懙摹！Ｐ姨澠瓷狭吮┝Σ蝗籘MD肯定一分也沒有。。最后改了cloverhxy的萬能質(zhì)數(shù)就過了。。

hash的思路還是比較顯然的，因?yàn)槲粩?shù)非常的少，所以可以暴力選擇某些位讓它們作為不相同的位，然后把這幾位在原串里面去掉，搞一坨hash值出來排個(gè)序就能知道到底幾對(duì)數(shù)字相等了。一開始覺得這么做就可以了但是發(fā)現(xiàn)算的亂七八糟答案多了好多。。這是為什么呢。。

原因就是它選出來的那幾位不一定全都是不相等的，因?yàn)槲覀冎皇恰凹傺b”那幾位在每一對(duì)串里面都不一樣然后強(qiáng)行把它摳出來，但是有可能選出來的某些位在某幾對(duì)串里面是相等的。也就是說題目中要求的是恰好k位不同，而我們算的是至多k位不同，所以說還得減去那些不同的位數(shù)比k少的。

然后這就是一個(gè)容斥的思路了。考慮有什么東西被多選了，每個(gè)被多選了幾次。以某一對(duì)串里面選定了2個(gè)字符讓它們相等為例，如果這兩個(gè)串是“aabc”和“aade”這種東西，也就是恰好有2個(gè)字符相等，那么肯定能正確的判定出來；但是如果是“aaab”和“aaac”這種有3個(gè)字符相等的東西，那么這三個(gè)相等的a我們?nèi)我饬粝聝蓚€(gè)，都會(huì)判定它們相等。也就是說這一對(duì)不合法的串被多計(jì)算了C23$C_3^2$次。

但是可以發(fā)現(xiàn)如果僅僅選出所有3個(gè)字符相等的串然后乘上C23$C_3^2$再減去答案還是不對(duì)的，這是因?yàn)槿绻@個(gè)串有4個(gè)字符相等，它們也會(huì)被重復(fù)計(jì)算然后多減去。首先在算2個(gè)字符相等的時(shí)候它們被多算了C24$C_4^2$次，然后在減去3個(gè)字符相等的時(shí)候它們每一個(gè)被重復(fù)計(jì)算了C34$C_4^3$次，每一次乘上一個(gè)C23$C_3^2$。可以發(fā)現(xiàn)它們被多減去了C24$C_4^2$次。要把這些都加回來。剩下的情況以此類推，在dfs的時(shí)候控制一下容斥系數(shù)就可以了。

代碼

請(qǐng)自行忽略奇怪的函數(shù)名和強(qiáng)行拼進(jìn)去的暴力。。。。