PSequence
标题描述
给定一个元素聚集 S S S，求 S S S 的全部排列满意对于恣意相邻两个元素 s 1 s_1 s1， s 2 s_2 s2， ( s 1 − s 2 ) (s_1−s_2) (s1−s2) 不被 P 整除。保证 S S S 中恣意两个元素都不相同。
输入格式
输入第一行一个数 n n n，表示聚集 S S S 的大小
以下 n n n 个数
末了一个数 P P P
输出格式
输出一个数，表述满意条件的排列的个数，模 12
34567891 12
34567891 12
34567891。
样例
input #1
output #1
数据范围及提示
对于 30 % 30\% 30% 的数据， n ≤ 9 n\leq 9 n≤9
对于 100 % 100\% 100% 的数据， n ≤ 30 n\leq 30 n≤30， S i ≤ 1 0 6 S_i\leq 10^6 Si≤106
注明
转载需经过本人同意。 转载需经过本人同意。 转载需经过本人同意。
解题思路
起首，若 s i s_i si、 s i + 1 s_{i+1} si+1 如果不符合条件，则 s 1 s_1 s1、 s 2 s_2 s2 模 p p p 同。那么你用 C C C 数组可以记下 S S S 内全部元素的值模 p p p 等于的各个数的个数，从大到小排序。设要在原序列选 k k k 个不合法， l l l 个合法的的位置插入，设 F i , j F_{i,j} Fi,j 表示处理了前 i i i 大的余数的数，有 j j j 对不合法的方案数的方案数。不难推出：
F i , j − k + C i − k − 1 + = F i − 1 , j × C j k × C s + 1 − j l × C c − 1 k + l − 1 F_{i,j-k+C_i-k-1}+=F_{i-1,j}\times C_j^k\times C_{s+1-j}^l\times C_{c-1}^{k+l-1} Fi,j−k+Ci−k−1+=Fi−1,j×Cjk×Cs+1−jl×Cc−1k+l−1
当罗列到 C C C 数组的值为 F i − 1 , 0 × Π C i ! F_{i-1,0}\times \Pi C_i! Fi−1,0×ΠCi!
Code
- #include<bits/stdc++.h>using namespace std;#define int long longconst int Maxn = 30 + 5, Maxval = 1e6 + 5, Mod = 12
- 34567891;int Fac[Maxn], InFac[Maxn];inline int Q_Pow(int x, int y) { int res = 1; while (y) { if (y & 1) res = res * x % Mod; x = x * x % Mod; y >>= 1; } return res;}inline int Get_C(int a, int b) { if (b > a || a < 0 || b < 0) return 0; return Fac[a] * InFac[b] % Mod * InFac[a - b] % Mod;}int n, s[Maxn], p;map<int, int>Map;int C[Maxval], Top, F[Maxn][Maxn];int Answer;inline bool Cmp(int a, int b) { return a > b;}signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); Fac[0] = 1; InFac[0] = 1; for (register int i = 1; i < Maxn; ++i) { Fac[i] = Fac[i - 1] * i % Mod; InFac[i] = InFac[i - 1] * Q_Pow(i, Mod - 2) % Mod; } cin >> n; for (register int i = 1; i <= n; ++i) cin >> s[i]; cin >> p; for (register int i = 1; i <= n; ++i) ++Map[(s[i] % p + p) % p]; for (auto [x, y] : Map) C[Top++] = y; sort(C, C + Top, Cmp); F[0][C[0] - 1] = 1; for (register int i = 1, s = C[0]; i <= n; ++i) { if (C[i] == 0) { for (register int j = 0; j < Top; ++j) (F[i - 1][0] *= Fac[C[j]]) %= Mod; cout << F[i - 1][0] << endl; exit(0); } for (register int j = 0; j <= s; ++j) for (register int k = 0; k <= C[i]; ++k) for (register int l = 0; l <= C[i]; ++l) if (j - k + C[i] - k - l >= 0) (F[i][j - k + C[i] - k - l] += F[i - 1][j] * Get_C(j, k) % Mod * Get_C(s + 1 - j, l) % Mod * Get_C(C[i] - 1, k + l - 1) % Mod) %= Mod; s += C[i]; } return 0;}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao12
3.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
