22分 5WA 2RE,求调
查看原帖
22分 5WA 2RE,求调
901195
__Luna__楼主2024/7/16 16:47
#include<iostream>
using namespace std;
const int MAXN = 2000001;
template<typename T>
struct NT;
template<> struct NT<short> { using type = long; };
template<> struct NT<int> { using type = std::conditional<sizeof(int) <= sizeof(short), long, long long>::type; };
template<> struct NT<long> { using type = long long; };
template<> struct NT<long long> { using type = __int128; };
template<typename T1, typename T2>
typename NT<typename std::conditional<sizeof(T1) >= sizeof(T2), T1, T2>::type>::type LT() { return 1; }
template<class T1, class T2, int M>
class NTT
{
	T1 P, G, _G;
	T2 L, R[M];
	T1 _L;
	bool type;
	T1 g(T1 n)
	{
		T1 r = 1, t = (P - 1) / n, a = type ? G : _G;
		while (t > 0)
		{
			if (t & 1) r = LT<T1, T2>() * r * a % P;
			a = LT<T1, T2>() * a * a % P;
			t >>= 1;
		}
		return r;
	}
public:
	NTT(T1 p, T1 g, T1 _g, T2 l): P(p), G(g), _G(_g)
	{
		type = true, L = 1;
		int t = 0;
		while(L <= l) L <<= 1, t++;
		_L = 1;
		T2 a = L;
		T1 z = P - 2;
		while (z > 0)
		{
			if (z & 1) _L = LT<T1, T2>() * _L * a % P;
			a = LT<T1, T2>() * a * a % P;
			z >>= 1;
		}
		for(int i = 0; i < L; i++) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (t - 1));	
	} 
	void operator()(T1* a)
	{
		for(int i = 0; i < L; i++) if(i < R[i]) a[i] ^= a[R[i]], a[R[i]] ^= a[i], a[i] ^= a[R[i]];
		for(int m = 1; m < L; m <<= 1) 
		{
			T1 _w_ = g(m << 1);
			for(int i = 0; i < L; i += (m << 1)){
                T1 w = 1;
                for(int j = 0; j < m; j++, w = LT<T1, T2>() * w * _w_ % P) {
				 T1 a1 = a[i + j], a2 = LT<T1, T2>() * w * a[i + j + m] % P;
				 a[i + j] = LT<T1, T2>() * (a1 + a2) % P, a[i + j + m] = LT<T1, T2>() * (a1 - a2 + P) % P;
			}
            }
		}
		if(!type)for(int i = 0; i < L; i++) a[i] = LT<T1, T2>() * a[i] * _L % P;	
	}
	NTT<T1, T2, M> operator~()
	{
		 NTT<T1, T2, M>c = *this;
		 c.type = !c.type;
		 return c;
	}
};
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int m, n;
	int a[MAXN], b[MAXN];
	cin >> m >> n;
	for(int i = 0; i <= m; i++) cin>>a[i];
	for(int i = 0; i <= n; i++) cin>>b[i];
	NTT<int, int, MAXN> ntt(998244353, 3, 332748118, m + n);
	ntt(a), ntt(b);
    for (int i = 0; i <= m + n; i++) a[i] = 1ll * a[i] * b[i] % 998244353;
    (~ntt)(a);
	for(int i = 0; i <= m + n; i++) cout << a[i] << " "; 
	return 0;
}

拜托大佬帮忙看看问题在哪里,为什么一些测试点不过。
另外,RE给的是:Segmentation fault with invalid memory reference.也帮忙看看为什么会出RE

2024/7/16 16:47
加载中...