시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB69161525.862%

문제

어떤 문자열 S의 길이가 k인 부분문자열의 집합을 T(S, k)라 표현하자. 예를 들어 S = "ABABA", k = 2일 때, T(S, k) = {"AB", "BA"}가 된다. {"AB", "BA", "AB", "BA"}가 아닌 이유는 집합은 같은 원소(중복된 원소)를 허용하지 않기 때문이다.

N 종류의 문자로 이루어진 길이가 k인 문자열들의 집합 X가 주어졌을 때, T(S, k)가 X의 부분집합이 되도록 하는 S의 개수를 구하는 프로그램을 작성하시오. 단 S의 길이는 L이어야 한다.

예를 들어 X = {"ABB", "BCA", "BCD", "CAB", "CDD", "DDA"}인 경우에는 "BCABB", "BCDDA"의 두 가지 경우가 있다.

입력

첫째 줄에 N(1 ≤ N ≤ 26), L(1 ≤ L ≤ 100), M(1 ≤ M ≤ 600)이 주어진다. M은 집합 X의 크기이다. 다음 줄에는 X를 이루는 문자열들이 주어진다. 각 문자열들의 길이는 같으며, 10 이하이다. 입력으로는 대문자만 주어진다.

출력

첫째 줄에 S의 개수를 출력한다. 이 값은 231-1보다 작거나 같다.

예제 입력 1

5 4 5
E D C B A

예제 출력 1

625

예제 입력 2

4 8 3
AA ZZ KK

예제 출력 2

3
W3sicHJvYmxlbV9pZCI6IjIzMTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjQgXHViY2Y1XHVjNmQwXHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIGtcdWM3NzggXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc0NCBUKFMsIGspXHViNzdjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1Yzc5MC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBTID0gJnF1b3Q7QUJBQkEmcXVvdDssIGsgPSAyXHVjNzdjIFx1YjU0YywgVChTLCBrKSA9IHsmcXVvdDtBQiZxdW90OywgJnF1b3Q7QkEmcXVvdDt9XHVhYzAwIFx1YjQxY1x1YjJlNC4geyZxdW90O0FCJnF1b3Q7LCAmcXVvdDtCQSZxdW90OywgJnF1b3Q7QUImcXVvdDssICZxdW90O0JBJnF1b3Q7fVx1YWMwMCBcdWM1NDRcdWIyY2MgXHVjNzc0XHVjNzIwXHViMjk0IFx1YzlkMVx1ZDU2OVx1Yzc0MCBcdWFjMTlcdWM3NDAgXHVjNmQwXHVjMThjKFx1YzkxMVx1YmNmNVx1YjQxYyBcdWM2ZDBcdWMxOGMpXHViOTdjIFx1ZDVjOFx1YzZhOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5OIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWUzOFx1Yzc3NFx1YWMwMCBrXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1YjRlNFx1Yzc1OCBcdWM5ZDFcdWQ1NjkgWFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBUKFMsIGspXHVhYzAwIFhcdWM3NTggXHViZDgwXHViZDg0XHVjOWQxXHVkNTY5XHVjNzc0IFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWIyOTQgU1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjJlOCBTXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBMXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBYID0geyZxdW90O0FCQiZxdW90OywgJnF1b3Q7QkNBJnF1b3Q7LCAmcXVvdDtCQ0QmcXVvdDssICZxdW90O0NBQiZxdW90OywgJnF1b3Q7Q0REJnF1b3Q7LCAmcXVvdDtEREEmcXVvdDt9XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDtCQ0FCQiZxdW90OywgJnF1b3Q7QkNEREEmcXVvdDtcdWM3NTggXHViNDUwIFx1YWMwMFx1YzljMCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOKDEgJmxlOyBOICZsZTsgMjYpLCBMKDEgJmxlOyBMICZsZTsgMTAwKSwgTSgxICZsZTsgTSAmbGU7IDYwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBNXHVjNzQwIFx1YzlkMVx1ZDU2OSBYXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yzc3NFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBYXHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI0ZTRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHViYjM4XHVjNzkwXHVjNWY0XHViNGU0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWFjMTlcdWM3M2NcdWJhNzAsIDEwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjXHViMjk0IFx1YjMwMFx1YmIzOFx1Yzc5MFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBTXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjMTJcdWM3NDAgMjxzdXA+MzE8XC9zdXA+LTFcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMzE5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGVjb3JhdGlvbnMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBTdWx0YW4gb2YgU3lsdmFuaWEgbG92ZXMgdGhyb3dpbmcgcGFydGllcywgYmVjYXVzZSB0aGF0IGdpdmVzIGhpbSBhIHJlYXNvbiB0byBkZWNvcmF0ZSB0aGUgcGFsYWNlLiBIZSBwYXJ0aWN1bGFybHkgbGlrZXMgZGVjb3JhdGlvbnMgY2FsbGVkIHN0cmVhbWVycyBtYWRlIHVwIG9mIGRpZmZlcmVudCBiZWFkcyBzdHJ1bmcgdG9nZXRoZXIgb24gYSBzdHJpbmcgYW5kIGh1bmcgZnJvbSB0aGUgY2VpbGluZy4gTm93LCBsaWtlIG1vc3QgU3VsdGFucywgaGUgaXMgdmVyeSBwYXJ0aWN1bGFyIGFib3V0IGV2ZXJ5dGhpbmcsIGluY2x1ZGluZyB0aGVzZSBzdHJ1bmcgZGVjb3JhdGlvbnMuIFNwZWNpJm1hY3I7Y2FsbHksIGhlIG9ubHkgbGlrZXMgY2VydGFpbiBjb21iaW5hdGlvbnMgb2YgYmVhZHMgdG8gYmUgdXNlZCBvbiB0aGUgc3RyZWFtZXJzLiBGb3IgZXhhbXBsZSwgaWYgdGhlcmUgYXJlIGZvdXIgZGkmcmVnO2VyZW50IHR5cGVzIG9mIGJlYWRzIC0gQSwgQiwgQyBhbmQgRCAtIHRoZSBTdWx0YW4gbWlnaHQgc2F5ICZxdW90O0l0IHBsZWFzZXMgaGlzIGhpZ2huZXNzIHRoYXQgb25seSB0aGUgY29tYmluYXRpb25zIEFCQiwgQkNBLCBCQ0QsIENBQiwgQ0REIGFuZCBEREEgYXBwZWFyIGluIHRoZSBzdHJlYW1lcnMgYXQgdG9uaWdodCYjMzk7cyBwYXJ0eSZxdW90Oy4gVGhpcywgbmVlZGxlc3MgdG8gc2F5LCBwdXRzIGEgc2V2ZXJlIGxpbWl0IG9uIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHN0cmVhbWVycyBwb3NzaWJsZS4gRm9yIGV4YW1wbGUsIGlmIHRoZSBsZW5ndGggb2YgdGhlIHN0cmVhbWVycyB3YXMgNSwgdGhlbiB0aGUgb25seSBwb3NzaWJsZSBzdHJlYW1zIG9mIGJlYWRzIHdvdWxkIGJlIEJDQUJCIGFuZCBCQ0REQSAoc3RyaW5ncyBzdWNoIGFzIEFCQkNBIGNvdWxkIG5vdCBiZSB1c2VkIGJlY2F1c2UgQkJDIGlzIG5vdCBhbiBhcHByb3ZlZCBjb21iaW5hdGlvbikuIFNpbmNlIHRoZSBTdWx0YW4gbGlrZXMgdmFyaWV0eSwgaXQgaXMgaW1wb3J0YW50IHRvIGtub3cgdGhlIHRvdGFsIG51bWJlciBvZiBzdHJlYW1lcnMgcG9zc2libGUsIGdpdmVuIGEgbGVuZ3RoIGFuZCB0aGUgY3VycmVudCBiZWFkIGNvbWJpbmF0aW9ucyB3aGljaCB0aWNrbGUgdGhlIFN1bHRhbiYjMzk7cyBmYW5jeS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IHdpbGwgY29uc2lzdCBvZiBtdWx0aXBsZSB0ZXN0IGNhc2VzLiBFYWNoIGNhc2Ugd2lsbCBjb25zaXN0IG9mIHR3byBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIHRocmVlIHBvc2l0aXZlIGludGVnZXJzIG4sIGwgYW5kIG0sIHdoZXJlIG4gaW5kaWNhdGVzIHRoZSBudW1iZXIgb2YgYmVhZCB0eXBlcywgbCBpcyB0aGUgbGVuZ3RoIG9mIHRoZSBzdHJlYW1lcnMgYW5kIG0gaW5kaWNhdGVzIHRoZSBudW1iZXIgb2YgYmVhZCBjb21iaW5hdGlvbnMgd2hpY2ggdGhlIFN1bHRhbiBsaWtlcy4gVGhlIG1heGltdW0gdmFsdWVzIGZvciBuLCBsIGFuZCBtIHdpbGwgYmUgMjYsIDEwMCBhbmQgNjAwLCByZXNwZWN0aXZlbHkuIFRoZSBuZXh0IGxpbmUgd2lsbCBjb250YWluIHRoZSBtIGNvbWJpbmF0aW9ucy4gRWFjaCBjb21iaW5hdGlvbiB3aWxsIGJlIG9mIHRoZSBzYW1lIGxlbmd0aCAoYmV0d2VlbiAxIGFuZCAxMCkgYW5kIHdpbGwgYmUgc2VwYXJhdGVkIHVzaW5nIGEgc2luZ2xlIHNwYWNlLiBBbGwgY29tYmluYXRpb25zIHdpbGwgbWFrZSB1c2Ugb2Ygb25seSB0aGUgdXBwZXJjYXNlIGxldHRlcnMgb2YgdGhlIGFscGhhYmV0LiBBbiBpbnB1dCBsaW5lIG9mIDAgMCAwIHdpbGwgdGVybWluYXRlIGlucHV0IGFuZCBzaG91bGQgbm90IGJlIHByb2Nlc3NlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBsaW5lIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiBwb3NzaWJsZSBzdHJlYW1lcnMuIEFsbCBhbnN3ZXJzIHdpbGwgYmUgd2l0aGluIHRoZSByYW5nZSBvZiBhIDMyLWJpdCBpbnRlZ2VyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > North America > East Central North America Regional > 2003 East Central Regional Contest B번

  • 잘못된 데이터를 찾은 사람: koosaga