jsp网站开发登陆,网站建设上海哪家公司好,公司宣传册排版,个人公益网站怎么制作AGC005D - ~K Perm Counting
Solution
经典数排列个数题#xff0c;写了个大麻烦容斥。
直接容斥#xff0c;考虑求出fif_ifi表示有iii个位置∣pi−i∣k|p_i-i|k∣pi−i∣k的方案数。一个位置iii满足∣pi−i∣k|p_i-i|k∣pi−i∣k#xff0c;要么piikp_iikpiik写了个大麻烦容斥。
直接容斥考虑求出fif_ifi表示有iii个位置∣pi−i∣k|p_i-i|k∣pi−i∣k的方案数。一个位置iii满足∣pi−i∣k|p_i-i|k∣pi−i∣k要么piikp_iikpiik要么pii−kp_ii-kpii−k当前面的位置选择了piikp_iikpiik时后面的pi2kp_{i2k}pi2k就不能选择ikikik了前面可能对后面产生影响。
因此我们发现对于下标modkmod\;kmodk不同的位置之间一定没有影响于是我们对modkmod\;kmodk余数分类拉出nmodkn\mod knmodk条长为⌊nk⌋1\lfloor\frac{n}{k}\rfloor1⌊kn⌋1的链和k−nmodkk-n\mod kk−nmodk条长为⌊nk⌋\lfloor\frac{n}{k}\rfloor⌊kn⌋的链此时∣pi−i∣k|p_i-i|k∣pi−i∣k等价于选择了该点在链上的相邻点把这些链的fff值用背包合并起来就是我们要求的fff。
于是我们要对每一种jjj算出一条链上选取jjj个的方案数。令gi,j,kg_{i,j,k}gi,j,k表示前iii点选取jjj个相邻点i−1,i,i1{i-1,i,i1}i−1,i,i1的选取状态为kkk的方案数。
最后的答案要算上没选的点的任意选取的排列个数即 Ans∑i0n(−1)ifi(n−i)!Ans\sum_{i0}^n(-1)^if_i(n-i)!Ansi0∑n(−1)ifi(n−i)!
时间复杂度O(n2)O(n^2)O(n2)据说也有O(nlgn)O(nlgn)O(nlgn)的更麻烦做法。
Code
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods924844033;
const int MAXN2005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
int num0,h[MAXN],g[MAXN][MAXN][8],f[MAXN],fac[MAXN],tmp[MAXN];
int upd(int x,int y) { return xymods?xy-mods:xy; }
void Merge(int q)
{for (int j0;jq;j) {h[j]0;for (int t0;t4;t) h[j]upd(h[j],g[q][j][t]);}numq;for (int j0;jnum;j) tmp[j]0;for (int jnum;j0;j--)for (int k0;kq;k) if (jk) tmp[j]upd(tmp[j],1ll*f[j-k]*h[k]%mods);for (int j0;jnum;j) f[j]tmp[j];
}
signed main()
{int nread(),pread(),qn/p1;fac[0]1;for (int i1;in;i) fac[i]1ll*fac[i-1]*i%mods;g[1][0][0]g[1][1][4]1;for (int i1;iq;i)for (int j0;ji;j){for (int k0;k8;k) g[i1][j][k1]upd(g[i1][j][k1],g[i][j][k]);for (int k0;k8;k){if (!((k1)1)) g[i1][j1][(k1)|1]upd(g[i1][j1][(k1)|1],g[i][j][k]);if (!((k1)4)) g[i1][j1][(k1)|4]upd(g[i1][j1][(k1)|4],g[i][j][k]);}}f[0]1;int rn%p; for (int i1;ir;i) Merge(q);for (int i1;ip-r;i) Merge(q-1);int ans0;for (int i0;in;i) if (i1) ansupd(ans,mods-1ll*f[i]*fac[n-i]%mods);else ansupd(ans,1ll*f[i]*fac[n-i]%mods);printf(%d\n,ans);return 0;
}
