PSequence 题解 DP
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
n
s1 s2 ... sn
P
输出格式
输出一个数，表述满意条件的排列的个数，模 12
34567891 12
34567891 12
34567891。
样例
input #1
4
1 2 3 4
3
output #1
12
数据范围及提示
对于 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, InFac;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 * InFac % Mod * InFac % Mod;}int n, s, p;map<int, int>Map;int C, Top, F;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 = 1; InFac = 1; for (register int i = 1; i < Maxn; ++i) { Fac = Fac * i % Mod; InFac = InFac * Q_Pow(i, Mod - 2) % Mod; } cin >> n; for (register int i = 1; i <= n; ++i) cin >> s; cin >> p; for (register int i = 1; i <= n; ++i) ++Map[(s % p + p) % p]; for (auto : Map) C = y; sort(C, C + Top, Cmp); F - 1] = 1; for (register int i = 1, s = C; i <= n; ++i) { if (C == 0) { for (register int j = 0; j < Top; ++j) (F *= Fac]) %= Mod; cout << F << endl; exit(0); } for (register int j = 0; j <= s; ++j) for (register int k = 0; k <= C; ++k) for (register int l = 0; l <= C; ++l) if (j - k + C - k - l >= 0) (F - k - l] += F * Get_C(j, k) % Mod * Get_C(s + 1 - j, l) % Mod * Get_C(C - 1, k + l - 1) % Mod) %= Mod; s += C; } return 0;} 然后你就秒了。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao12
3.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]