首页 > 其他分享 >洛谷 P5293 [HNOI2019] 白兔之舞

洛谷 P5293 [HNOI2019] 白兔之舞

时间：2024-04-29 12:44:25浏览次数：24  
标签：node mod1 mod3 洛谷 int const HNOI2019 P5293 mod

洛谷传送门

所求即为：

\[\begin{aligned} f_t & = \sum\limits_{m = 0}^L \binom{L}{m} A^m [k \mid m - t] \\ & = \frac{1}{k} \sum\limits_{m = 0}^L \binom{L}{m} A^m \sum\limits_{i = 0}^{k - 1} \omega_k^{i(m - t)} \\ & = \frac{1}{k} \sum\limits_{i = 0}^{k - 1} \omega_k^{-it} \sum\limits_{m = 0}^L \binom{L}{m} A^m \\ & = \frac{1}{k} \sum\limits_{i = 0}^{k - 1} \omega_k^{-it} (I + A)^L \end{aligned} \]

接下来是一个 IDFT 的模板，直接套 Bluestein's Algorithm 即可。

code 
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 500100;
const int G = 3, mod1 = 998244353, mod2 = 1004535809, mod3 = 469762049;
const lll M = (lll)mod1 * mod2 * mod3;

inline ll qpow(ll b, ll p, const int &mod) {
	ll res = 1;
	while (p) {
		if (p & 1) {
			res = res * b % mod;
		}
		b = b * b % mod;
		p >>= 1;
	}
	return res;
}

const lll I0 = (M / mod1) * qpow((M / mod1) % mod1, mod1 - 2, mod1);
const lll I1 = (M / mod2) * qpow((M / mod2) % mod2, mod2 - 2, mod2);
const lll I2 = (M / mod3) * qpow((M / mod3) % mod3, mod3 - 2, mod3);

int n, K, L, X, Y, mod;

struct node {
	int x, y, z;
	node(int a = 0, int b = 0, int c = 0) : x(a), y(b), z(c) {}
	
	inline int get() {
		return (x * I0 + y * I1 + z * I2) % M % mod;
	}
} pw[maxn >> 1];

inline node operator + (const node &a, const node &b) {
	return node(a.x + b.x < mod1 ? a.x + b.x : a.x + b.x - mod1, a.y + b.y < mod2 ? a.y + b.y : a.y + b.y - mod2, a.z + b.z < mod3 ? a.z + b.z : a.z + b.z - mod3);
}

inline node operator - (const node &a, const node &b) {
	return node(a.x < b.x ? a.x - b.x + mod1 : a.x - b.x, a.y < b.y ? a.y - b.y + mod2 : a.y - b.y, a.z < b.z ? a.z - b.z + mod3 : a.z - b.z);
}

inline node operator * (const node &a, const node &b) {
	return node(1LL * a.x * b.x % mod1, 1LL * a.y * b.y % mod2, 1LL * a.z * b.z % mod3);
}

typedef vector<node> poly;

int r[maxn];

typedef vector<node> poly;

inline void NTT(poly &a, int op) {
	int n = (int)a.size();
	for (int i = 0; i < n; ++i) {
		if (i < r[i]) {
			swap(a[i], a[r[i]]);
		}
	}
	for (int k = 1; k < n; k <<= 1) {
		node wn(qpow(op == 1 ? G : qpow(G, mod1 - 2, mod1), (mod1 - 1) / (k << 1), mod1), qpow(op == 1 ? G : qpow(G, mod2 - 2, mod2), (mod2 - 1) / (k << 1), mod2), qpow(op == 1 ? G : qpow(G, mod3 - 2, mod3), (mod3 - 1) / (k << 1), mod3));
		pw[0] = node(1, 1, 1);
		for (int i = 1; i < k; ++i) {
			pw[i] = pw[i - 1] * wn;
		}
		for (int i = 0; i < n; i += (k << 1)) {
			auto i1 = a.begin() + i, i2 = a.begin() + i + k;
			node *p = pw;
			int j = 0;
			while (j + 7 < k) {
				node x = *i1, y = (*p) * (*i2);
				*i1 = x + y;
				*i2 = x - y;
				x = *(++i1);
				y = (*(++p)) * (*(++i2));
				*i1 = x + y;
				*i2 = x - y;
				x = *(++i1);
				y = (*(++p)) * (*(++i2));
				*i1 = x + y;
				*i2 = x - y;
				x = *(++i1);
				y = (*(++p)) * (*(++i2));
				*i1 = x + y;
				*i2 = x - y;
				x = *(++i1);
				y = (*(++p)) * (*(++i2));
				*i1 = x + y;
				*i2 = x - y;
				x = *(++i1);
				y = (*(++p)) * (*(++i2));
				*i1 = x + y;
				*i2 = x - y;
				x = *(++i1);
				y = (*(++p)) * (*(++i2));
				*i1 = x + y;
				*i2 = x - y;
				x = *(++i1);
				y = (*(++p)) * (*(++i2));
				*(i1++) = x + y;
				*(i2++) = x - y;
				++p;
				j += 8;
			}
			while (j < k) {
				node x = *i1, y = (*p) * (*i2);
				*i1 = x + y;
				*i2 = x - y;
				++j;
				++i1;
				++i2;
				++p;
			}
		}
	}
	if (op == -1) {
		node inv(qpow(n, mod1 - 2, mod1), qpow(n, mod2 - 2, mod2), qpow(n, mod3 - 2, mod3));
		for (int i = 0; i < n; ++i) {
			a[i] = a[i] * inv;
		}
	}
}

inline void conv(poly &a, poly &b) {
	NTT(a, 1);
	NTT(b, 1);
	int n = (int)a.size();
	for (int i = 0; i < n; ++i) {
		a[i] = a[i] * b[i];
	}
	NTT(a, -1);
}

inline vector<int> mul(const vector<int> &a, const vector<int> &b) {
	int n = (int)a.size() - 1, m = (int)b.size() - 1, k = 0;
	while ((1 << k) <= n + m + 1) {
		++k;
	}
	for (int i = 1; i < (1 << k); ++i) {
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (k - 1));
	}
	poly A(1 << k), B(1 << k);
	for (int i = 0; i <= n; ++i) {
		A[i] = node(a[i], a[i], a[i]);
	}
	for (int i = 0; i <= m; ++i) {
		B[i] = node(b[i], b[i], b[i]);
	}
	conv(A, B);
	vector<int> res(n + m + 1);
	for (int i = 0; i <= n + m; ++i) {
		res[i] = A[i].get();
	}
	return res;
}

inline vector<int> bls(int n, int m, int w, vector<int> &a) {
	static int pw[maxn], ipw[maxn];
	pw[0] = pw[1] = ipw[0] = ipw[1] = 1;
	int iw = qpow(w, mod - 2, mod);
	for (int i = 2; i <= max(n, m) + 1; ++i) {
		pw[i] = 1LL * pw[i - 1] * w % mod;
		ipw[i] = 1LL * ipw[i - 1] * iw % mod;
	}
	for (int i = 2; i <= max(n, m) + 1; ++i) {
		pw[i] = 1LL * pw[i - 1] * pw[i] % mod;
		ipw[i] = 1LL * ipw[i - 1] * ipw[i] % mod;
	}
	vector<int> b(n + 1), c(n + m + 1);
	for (int i = 0; i <= n + m; ++i) {
		if (i <= n) {
			b[i] = 1LL * a[i] * pw[i + 1] % mod;
		}
		c[i] = ipw[i >= n ? i - n : n - i + 1];
	}
	vector<int> d = mul(b, c), res(m + 1);
	for (int i = 0; i <= m; ++i) {
		res[i] = 1LL * pw[i] * d[i + n] % mod;
	}
	return res;
}

struct mat {
	int a[3][3];
	mat() {
		mems(a, 0);
	}
} a;

inline mat operator * (const mat &a, const mat &b) {
	mat res;
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				res.a[i][j] = (res.a[i][j] + 1LL * a.a[i][k] * b.a[k][j]) % mod;
			}
		}
	}
	return res;
}

inline mat qpow(mat a, ll p) {
	mat res;
	for (int i = 0; i < n; ++i) {
		res.a[i][i] = 1;
	}
	while (p) {
		if (p & 1) {
			res = res * a;
		}
		a = a * a;
		p >>= 1;
	}
	return res;
}

inline bool check(int x) {
	vector<int> vc;
	int y = mod - 1;
	for (int i = 2; i * i <= y; ++i) {
		if (y % i == 0) {
			vc.pb(i);
			while (y % i == 0) {
				y /= i;
			}
		}
	}
	if (y > 1) {
		vc.pb(y);
	}
	for (int t : vc) {
		if (qpow(x, (mod - 1) / t, mod) == 1) {
			return 0;
		}
	}
	return 1;
}

void solve() {
	scanf("%d%d%d%d%d%d", &n, &K, &L, &X, &Y, &mod);
	--X;
	--Y;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			scanf("%d", &a.a[i][j]);
		}
	}
	int g = -1;
	for (int i = 2;; ++i) {
		if (check(i)) {
			g = i;
			break;
		}
	}
	int w = qpow(g, (mod - 1) / K, mod);
	int iw = qpow(w, mod - 2, mod);
	vector<int> b(K);
	for (int i = 0; i < K; ++i) {
		int wi = qpow(w, i, mod);
		mat t = a;
		for (int j = 0; j < n; ++j) {
			for (int k = 0; k < n; ++k) {
				t.a[j][k] = 1LL * t.a[j][k] * wi % mod;
			}
		}
		for (int j = 0; j < n; ++j) {
			t.a[j][j] = (t.a[j][j] + 1) % mod;
		}
		t = qpow(t, L);
		b[i] = t.a[X][Y];
	}
	vector<int> res = bls(K - 1, K - 1, iw, b);
	int inv = qpow(K, mod - 2, mod);
	for (int i = 0; i < K; ++i) {
		printf("%lld\n", 1LL * res[i] * inv % mod);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签：node,mod1,mod3,洛谷,int,const,HNOI2019,P5293,mod
From： https://www.cnblogs.com/zltzlt-blog/p/18165420

相关文章

  • 洛谷题单指南-动态规划2-P1004 [NOIP2000 提高组] 方格取数
    原题链接：https://www.luogu.com.cn/problem/P1004题意解读：从起点走到终点，走两次，计算最大路径和，第一次走过的点数值变为0。解题思路：直观上思考，可以先从起点走到终点，计算最大路径和，并记录走过的所有点，然后把所有点的数值置为0，再从起点走到终点，计算最大路径和，把两次的最大路径......
  • 洛谷 P10084 [GDKOI2024 提高组] 计算
    洛谷传送门第一步是一个经典结论，\(L=m^{\gcd(a,b)}+1\)，\(R=m^{\gcd(c,d)}\)。因为\(L\equiv1\pmodm\)且\(R\equiv0\pmodm\)，所以可以把问题的范围改成\([1,n=R-L+1]\)。写出选数的生成函数：\[F(x)=\prod\limits_{i=1}^n(1+x^i)\]我们希望求......
  • 题解：洛谷 P1137 旅行计划
    标签：图论，拓扑，dp题意给定一张\(n\)个点\(m\)条边的DAG，对于每个\(i\)，求以它为终点最多经过多少个点？思路由于是DAG，求的是终点\(i\)经过的所有点，而刚好拓扑序就满足这个。那么就可以考虑拓扑排序。设\(f_i\)是以\(i\)为终点的最多结点数，那么就有转移方程\(f_v=m......
  • 洛谷P5597 复读
    洛谷P5597复读首先概括一下题意：文中给出三个指令L（命令机器人向当前节点的左子节点走）、R（命令机器人向当前节点的右子节点走）、U（命令机器人向当前节点的父亲节点走）以及一颗二叉树。初始状态，机器人在二叉树的根节点。当机器人处于二叉树的根节点时，不可以执行指令U，但是机器人可以走......
  • 「洛谷」题解：P1008 三连击
    题目传送门题目背景本题为提交答案题，您可以写程序或手算在本机上算出答案后，直接提交答案文本，也可提交答案生成程序。题目描述将\(1,2,\ldots,9\)共\(9\)个数分成\(3\)组，分别组成\(3\)个三位数，且使这\(3\)个三位数构成\(1:2:3\)的比例，试求出所有满足条件的......
  • 洛谷题单指南-动态规划2-P2679 [NOIP2015 提高组] 子串
    原题链接：https://www.luogu.com.cn/problem/P2679题意解读：在a中按顺序挑选k个子串，使得这些子串连在一起正好和b相等，求方案数。解题思路：这样的题目，无外乎两个思路：DFS暴搜（得部分分）、动态规划动态规划不好想，还是先暴搜吧！1、DFS暴搜搜索的思路就是：从a起始位置开始，一直找到跟b前......
  • [题解] [洛谷P4158] 粉刷匠
    [题解][洛谷P4158]粉刷匠题目描述有\(n\)个木板，每个木板有\(m\)个格子，所有格子最开始视为没有颜色。有\(0/1\)两种颜色，每次可以粉刷其中一块木板上一段连续的格子，总共可以粉刷\(t\)次。给出一组目标颜色，问最多可以将多少个格子粉刷成目标颜色。输入格式第一行包含......
  • 洛谷题单指南-动态规划2-P1439 【模板】最长公共子序列
    原题链接：https://www.luogu.com.cn/problem/P1439题意解读：求最长公共子序列的长度。解题思路：1、O(n^2)的方法：动态规划设两个排列为a，b设dp[i][j]表示a[1~i]与b[1~j]的最长公共子序列长度根据公共子序列结尾是否包含a[i]、b[j]是否相等分情况讨论：如果a[i]==b[j]  则结尾......
  • 洛谷题解-官方题单-递归与递推
    P1255数楼梯原题链接题目描述楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。编一个程序，计算共有多少种不同的走法。对于60%的数据，N≤50；对于100%的数据，1≤N≤5000。思路：每次有2种方法上楼梯，要么上一阶，要么上二阶。第一种：得50分的做法是可以用递归来解：点击查看代码......
  • 洛谷题单指南-动态规划2-P2758 编辑距离
    原题链接：https://www.luogu.com.cn/problem/P2758题意解读：对a字符串最少操作几次可以变成b字符串，看似无从下手，可以从内部递推关系着手。解题思路：设dp[i][j]表示将a字符串1~i变成b字符串1~j的最少操作次数，字符串下标从1开始。如何思考递推？可以从最后一步为切入点！最后一步对a[i]......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99