提出 #29017539

---

ソースコード 拡げる

/*
    Author : SharpnessV & SharpnessX
    Right Output ! & Accepted !
*/
#include<bits/stdc++.h>
//#include<atcoder/all>
#define int long long

#define rep(i, a, b) for(int i = (a);i <= (b);i++)
#define pre(i, a, b) for(int i = (a);i >= (b);i--)
#define rp(i, a) for(int i = 1; i <= (a); i++)
#define pr(i, a) for(int i = (a); i >= 1; i--)
#define go(i, x) for(auto i : x)

#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define si(x) (int)(x).size()
#define pc putchar
#define gc getchar
#define el putchar('\n')

using namespace std;
const double eps = 1e-15, pi = 3.1415926535897932385;
typedef long long LL;
typedef pair<int,int> Pr;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}, inf = 0x7fffffff, inf_ = 0x80000000;
const LL Inf = 0x7fffffffffffffffLL, Inf_ = 0x8000000000000000LL;
//Author : SharpnessV & SharpnessX
//#define main Solution
//char buf[1<<22],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T> inline void read(T &x) {
    x = 0;bool flag = false; char ch = getchar();
    while (ch < '0' || ch > '9')flag = ch == '-' ? true : false, ch = getchar();
    while (ch >= '0' && ch <= '9')x = (x << 3) + (x << 1) + (ch & 15), ch = getchar();
    if(flag) x = -x;
}
int gcd(int x,int y) {	return y ? gcd(y, x % y) : x;}
int lcm(int x,int y) {	return x / gcd(x, y) * y;}
//#define P 1000000007
#define P 998244353
#define bas 229
template<typename T> void cmx(T &x, T y){if(y > x) x = y;}
template<typename T> void cmn(T &x, T y){if(y < x) x = y;}
template<typename T> void ad(T &x, T y) {x += y; if(x >= P) x -= P;}
template<typename T> void su(T &x, T y) {x -= y; if(x < 0) x += P;}
int Pow(int x, int y){
	int now = 1 ;
	for(; y; y >>= 1, x = 1LL * x * x % P)if(y & 1) now = 1LL * now * x % P;
	return now;
}

/***************************************************************************************************************************/
/*                                                                                                                         */
/***************************************************************************************************************************/
int c[4] = {0, 1, 3, 0};
struct node{
	int x, y, v;
	bool operator<(const node o)const{
		if(x != o.x)return x < o.x;
		if(y != o.y)return y < o.y;
		return v < o.v;
	}
};
map<node,int>h;
int calc(int l,int r,int v){
	if(!v)return (min(l, r) + 1) % P;
	if(!l && !r)return 0;
	node cur{l, r, v};
	if(h.count(cur))return h[cur];
	int sum = 0;
	rep(x, 0, 1){
		int y = (v ^ x) & 1;
		if(x > l || y > r)continue;
		ad(sum, calc((l - x) / 2, (r - y) / 2, v / 2));
	}
	return h[cur] = sum;
}
int ask(int l,int r,int v){
	if(l < 0)return 0;
	int ans = 0;
	rep(i, 0, 3)rep(j, 0, 3){
		int w = v ^ c[i] ^ c[j];
		if(i > l || j > r)continue;
		int p = (l - i) / 4, q = (r - j) / 4;
		if(w % 4)continue;
		if(i & 1){
			if(j & 1){
				if(!w)ad(ans, ((p + 1) % P) * ((q + 1) % P) % P);
			}
			else{
				if(w / 4 <= q)ad(ans, (p + 1) % P);
			}
		}
		else{
			if(j & 1){
				if(w / 4 <= p)ad(ans, (q + 1) % P);
			}
			else{
				//cout << "ss " << p << " " << q << " " << w / 4 << " " << calc(p, q, w / 4) << endl;
				h.clear();
				ad(ans, calc(p, q, w / 4));
			}
		}
	}
	if(!v)su(ans, min(l, r) + 1);
	return ans;
}
int l, r, v;
signed main() {
	read(l), read(r), read(v), l --;
	int ans = ((ask(r, r, v) - 2 * ask(l - 1, r, v) + ask(l - 1, l - 1, v)) % P + P) % P;
	cout << ans * ((P + 1) / 2) % P << endl;
	return 0;
}

提出情報

ジャッジ結果