競技プログラミング用 知識集積所
ABC418D - XNOR Operation
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
通常のXORであれば、Sの中の1の個数が奇数ならば1、偶数個であれば0になる。
NXORはその0と1の立場が逆になる。
つまり、Sの中の0の個数が奇数ならば0、偶数個であれば1になる。
ということで、問題は実は「0の個数が偶数である部分文字列はいくつあるか？」である。
NXORはその0と1の立場が逆になる。
つまり、Sの中の0の個数が奇数ならば0、偶数個であれば1になる。
ということで、問題は実は「0の個数が偶数である部分文字列はいくつあるか？」である。
これは動的計画法で求められる。
つまり、
つまり、
- その文字で終わる、0が偶数個の文字列の数
- その文字で終わる、0が奇数個の文字列の数
を順に求めていき、偶数個の方の総和が答え。
解答例
注意点
答えがint型に入らない場合がある
全部oで最大文字数用意されると、答えは10^10くらいまでありうる。
long long型を用意しておくこと。
long long型を用意しておくこと。
