求助,为啥我慢
查看原帖
求助,为啥我慢
49093
_sys楼主2020/6/9 18:37

log\log 做法,就是过不去

#include <bits/stdc++.h>
using namespace std;

const int Maxn = 1 << 18 | 5, p = 167772161;
int rev[Maxn];
void get_rev(int len)
{
	for (int i = 0; i < len; i++)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (len >> 1));
}
long long fast_pow(long long x, long long y)
{
	long long ans = 1, now = x;
	while (y)
	{
		if (y & 1) ans = ans * now % p;
		now = now * now % p;
		y >>= 1;
	}
	return ans;
}
const long long inv3 = fast_pow(3, p - 2);
void NTT(int now[], int len, bool type = false)
{
	for (int i = 0; i < len; i++)
		if (i < rev[i]) swap(now[i], now[rev[i]]);
	for (int i = 1; i < len; i <<= 1)
	{
		int w = fast_pow(type ? inv3 : 3, (p - 1) / (i << 1));
		for (int j = 0; j < len; j += (i << 1))
		{
			int l = 1;
			for (int k = j; k < i + j; k++, l = l * (long long) w % p)
			{
				int x = now[i + k] * (long long) l % p, y = now[k];
				now[k] = (x + y) % p;
				now[i + k] = (y - x + p) % p;
			}
		}
	}
	if (type)
	{
		long long inv = fast_pow(len, p - 2);
		for (int i = 0; i < len; i++)
			now[i] = now[i] * inv % p;
	}
}
void fast_pow(int now[], int ans[], int len, int y)
{
	get_rev(len << 1);
	ans[0] = 1;
	static int tmp[Maxn];
	memset(tmp, 0, sizeof(int[len << 1]));
	memcpy(tmp, now, sizeof(int[len]));
	while (y)
	{
		NTT(tmp, len << 1);
		if (y & 1)
		{
			NTT(ans, len << 1);
			for (int i = 0; i < (len << 1); i++) ans[i] = ans[i] * (long long) tmp[i] % p;
			NTT(ans, len << 1, true);
			for (int i = len; i < (len << 1); i++) ans[i] = 0;
		}
		for (int i = 0; i < (len << 1); i++)
			tmp[i] = tmp[i] * (long long) tmp[i] % p;
		NTT(tmp, len << 1, true);
		for (int i = len; i < (len << 1); i++) tmp[i] = 0;
		y >>= 1;
	}
}
int lower(int x)
{
	int tmp = 1;
	for (; tmp < x; tmp <<= 1);
	return tmp;
}
int n, k;
long long now = 1;
int A[Maxn], B[Maxn];
int main()
{
	scanf("%d%d", &n, &k);
	int len = lower(n + 1);
	A[1] = 1;
	for (int i = 2; i < len; i++)
	{
		A[i] = A[p % i] * (long long) (p - p / i) % p;
		if (i <= k) (now *= A[i]) %= p;
	}
	fast_pow(A, B, len, k);
	for (int i = 0; i <= n; i++)
		printf("%lld ", B[i] * now % p), (now *= i + 1) %= p;
	return 0;
}
2020/6/9 18:37
加载中...