ABC129 E - Sum Equals Xor
April 15, 2020
問題
考えたこと
桁DPっぽいなぁ
とりあえずまず条件を満たすのはどういう時かを考えよう
a XOR b == a+b になる数
まずシンプルに1桁だけで考えてみる
| a | b | a XOR b | a + b |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 10 |
a,bが0,0 or 1,0 or 0,1のいずれかの場合はa XOR b == a + bになる
次に繰り上がりが発生した場合にa XOR b == a + bとなることがあるかを考える
(これがある場合は複雑そう..)
a,bを2桁で考えて, 繰り上がりが発生するように1桁目を1で固定して考えてみる
| a | b | a XOR b | a + b |
|---|---|---|---|
| 01 | 01 | 0 | 10 |
| 01 | 11 | 10 | 100 |
| 11 | 01 | 10 | 100 |
| 11 | 11 | 0 | 110 |
桁上がりが発生する場合はa XOR b != a + bになりそう。
ということで、1桁づつ考えていって良さそう.
a XOR b == a + bという条件だけであれば, 答えはpow(3通り, Lの桁数)で良さそう
(各桁で条件を満たすa,bの値は3通り,それを桁数なのでpowをとる)
これを基本として、もう1つの条件a + b <= Lを満たす場合を考える
a + b <= L を満たす場合は？
とりあえず小さい値でシミュレートしてみるL=1000として考えてみる
先頭から1つづつ取れる値を考えてみる
1桁目としてあり得るa,bの組み合わせとしてはa=1***, b=0***, a=0***, b=1***, a=0***, b=0***の3通り(*は未定とする)a + b == Lが許容される かつ 前節で確認したようにこれ以降の桁で繰り上がりが発生することはないので
まずa=1***, b=0***, a=0***, b=1***の2つを考える
Lの2桁目は0なので、これらの2桁目も0しか取れない(1にしてしまうと、a + b > Lになってしまう)
同様にLの3,4桁目も0なので、残りは全て0になって、1桁目をa=1***, b=0***, a=0***, b=1***とした場合に取り得る値は結局
a=1000, b=0000, a=0000, b=1000の2つだけになる
次に1桁目をa=0***, b=0***とした場合を考える
前節で確認したようにこれ以降の桁で繰り上がりが発生することはないので、これ以降の桁はa XOR b == a + bになる組み合わせ(３通り)の全てが許容される
これにより1桁目をa=0***, b=0***とした場合は3^3=27通りの組み合わせがあり得る
(例としてはa=0100, b=0001, a=0110, b=0000など)
答えとしては2+27 = 29となる
前の例は1桁目以外が全て0だったので簡単だった、次に先頭以外にも1が出てくるLを考えてみるL=1010として考える
1桁目としてあり得るa,bの組み合わせとしては前の例と同じくa=1***, b=0***, a=0***, b=1***, a=0***, b=0***の3通りa=0***, b=0***以降の桁は前の例と同じなので割愛
a=1***, b=0***, a=0***, b=1***を考える
Lの2桁目は0なので、これらの2桁目も0しか取れないのでa=10**, b=00**, a=00**, b=10**
問題は3桁目でここでLの3桁目が1なので
1桁目の時と同様に, a,bの組み合わせとして3通りが考えられる
つまりa=101*, b=000*, a=100*, b=001*, a=100*, b=000*a=001*, b=100*, a=000*, b=101*, a=000*, b=100*
ここで、a=100*, b=000*とa=000*, b=100*を考える
a,bの3桁目を両方0にすると、前述の通り、以降の桁でどの組み合わせを選ぼうともa + b > Lになることはないので
これら2つの4桁目は3通り取れる
a=101*, b=000*, a=100*, b=001*, a=001*, b=100*, a=000*, b=101*
の4つは4桁目でa + b > Lにならないようにしないといけない
Lの4桁目は0なのでこれらが取り得る値も0となりa=1010, b=0000, a=1000, b=0010, a=0010, b=1000, a=0000, b=1010
の4通りとなる
解としては、1桁目でa,bともに0とした場合の3^3 = 27
3桁目でa,bともに0とした場合の3^1 = 3が1桁目a=1, b=0, a=0,b=1の2パターンであるので3*2=6
最後に1,3桁目でa=1,b=0, a=0,b=1を選んだ場合の4パターン
全て合わせて27+6+4 = 37となる
結局答えは？
a,bが3通り選べる時にa=1,b=0, a=0,b=1の2つと, a=0,b=0で分けて考えていくと良い
Lを先頭から1つづつ見て行ってL[i]='1'のときa=1,b=0, a=0,b=1を選んだ場合が何通りあるか(これはpow(2, Lの中での1の出現回数)になる)
とL[i]='1'のとき、pow(3, Lの残り桁数) * pow(2, Lのこれまで見た桁の中での1の出現回数)
これらを足した数になる
計算量としてはpowの計算がO(logN)なのでO(NlogN)になる
提出したコード
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
typedef pair<ll, ll> P;
ll modnum = 1000000000+7;
long long modpow(long long a, long long n, long long mod) {
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
int main() {
string l; cin >> l;
ll ans = 0;
ll tmpans = 1;
rep(i, l.size()) {
int n = l[i] - '0';
if(n == 1) {
ll x = modpow(3, l.size()-1-i, modnum);
ans += x * tmpans;
ans %= modnum;
tmpans *= 2;
tmpans %= modnum;
}
}
ans += tmpans;
ans %= modnum;
cout << ans << endl;
return 0;
}
正しい解法
実際は桁DPやるっぽい
https://youtu.be/L8grWxBlIZ4?t=5360