ARC 084 F XorShift
http://arc084.contest.atcoder.jp/tasks/arc084_d
多項式への言い換えが気持ちがいい問題だった。多項式は気持ちがいい。
#include <iostream> #include <algorithm> #include <vector> using namespace std; const long long mod = 998244353; string gcd(string a, string b) { while (true) { if (a.size() < b.size()) swap(a, b); for (int i = 0; i < b.size(); i++) { a[i] ^= b[i]; } int pos = a.find(1); if (pos == string::npos) return b; a.erase(0, pos); } } string input() { string s; cin >> s; for (char &c : s) c -= '0'; return s; } long long modpow(long long x, long long y) { long long ret = 1; while (y > 0) { if (y & 1) ret = ret * x % mod; x = x * x % mod; y >>= 1; } return ret; } int main() { int n; cin >> n; string x = input(); string g = input(); for (int i = 1; i < n; i++) { g = gcd(g, input()); } long long ans = 0; string curr(x.size(), 0); for (int i = 0; i + g.size() <= x.size(); i++) { if (curr[i] == 0 && x[i] == 0) { // can't use } else if (curr[i] == 1 && x[i] == 0) { for (int j = 0; j < g.size(); j++) { curr[i + j] ^= g[j]; } } else if (curr[i] == 0 && x[i] == 1) { for (int j = 0; j < g.size(); j++) { curr[i + j] ^= g[j]; } ans += modpow(2, x.size() - i - g.size()); ans %= mod; } else if (curr[i] == 1 && x[i] == 1) { ans += modpow(2, x.size() - i - g.size()); ans %= mod; } } if (curr <= x) { ans++; ans %= mod; } cout << ans << endl; }