首页 > 其他分享 >【题解】TEST 22.11.21 - 计数(感谢强大艾尔法!!1)

【题解】TEST 22.11.21 - 计数(感谢强大艾尔法!!1)

时间:2022-11-21 21:25:28浏览次数:64  
标签:frac 21 int 题解 end 22.11 mul aligned mod

我们要求的是:

\[\begin{aligned} G(x)&=\sum_{i\geq 0}(i+n-m)!(-1)^{m-i}x^i\\ G'(x)&=\sum_{i\geq 1}i(i+n-m)!(-1)^{m-i}x^{i-1} \end{aligned} \]

考虑凑 \(\sum\limits_{i\geq 1}(i+n-m)!(-1)^{m-i}x^i\):

\[\begin{aligned} -x((n-m+1)G(x)+xG'(x))&=\sum\limits_{i\geq 1}(i+n-m)!(-1)^{m-i}x^i\\ &=G(x)+(-1)^{m-1}(n-m)! \end{aligned} \]

因此:

\[\begin{aligned} x^2G'(x)&=-[(n-m+1)x+1]G(x)+(-1)^{m}(n-m)!\\ F^2G'(F)&=-[(n-m+1)F+1]G(F)+(-1)^{m}(n-m)!\\ F^2\frac{[G(F)]'}{F'}&=-[(n-m+1)F+1]G(F)+(-1)^{m}(n-m)!\\ \end{aligned} \]

考虑到 \(F=\frac{x+x^2}{1-x},F'=\frac{(1+2x)(1-x)+(x+x^2)}{(1-x)^2}\),带入:

\[\begin{aligned} F^2\frac{[G(F)]'}{F'}&=-[(n-m+1)F+1]G(F)+(-1)^{m}(n-m)!\\ (x+x^2)^2\frac{[G(F)]'}{(1+2x)(1-x)+(x+x^2)}&=-\frac{(n-m+1)(x+x^2)+1-x}{1-x}G(F)+(-1)^{m}(n-m)!\\ \end{aligned} \]

于是:

\[(x+x^2)^2(1-x)[G(F)]'=\\ -[(n-m+1)(x+x^2)+1-x][1+2x-x^2]G(F)+(-1)^{m}(n-m)!(1-x)(1+2x-x^2)\\ \]

后面的最高项是 \(x^3\),是用来赋初值的。剩下的对比系数:

\[\begin{aligned} [x^m](x+x^2)^2(1-x)[G(F)]'&=-[x^m][(n-m+1)(x+x^2)+1-x][1+2x-x^2]G(F)\\ \end{aligned} \]

别以为初值就是子问题!注意 \(m\) 是不变的!

const int N = 1e7 + 5;

int n, m, L[6], R[5], H[6], G[N];

signed main () {
	IN (n), IN (m);

	// get L
	L[1] = 1;
	L[2] = 1;
	L[3] = mod - 1;
	L[4] = mod - 1;

	// get R
	R[0] = 1;
	R[1] = n - m;
	R[2] = n - m + 1;
	rep (i, 2, 0) {
		pls (R[i + 2], mul (mod - 1, R[i]));
		pls (R[i + 1], mul (2, R[i]));
	}

	// get fac[n - m]
	int pot = (n - m) / B, buf = rec[pot];
	lep (i, pot * B + 1, n - m) buf = mul (buf, i);

	int fix = qpow (mod - R[0], mod - 2);
	int ori = mul (((m & 1) ? mod - 1 : 1), buf);

	lep (i, 0, m) {
		lep (j, 1, min (4, i)) {
			pls (G[i], mul (L[j], mul (i - j, G[i - j])));
			pls (G[i], mul (R[j], G[i - j]));
		}

		if (i <= 3) sub (G[i], mul ((i == 2 ? mod - 3 : 1), ori));
		G[i] = mul (fix, G[i]);
	}

	printf ("%d\n", G[m]);
	return 0;
}

标签:frac,21,int,题解,end,22.11,mul,aligned,mod
From: https://www.cnblogs.com/qiulyqwq/p/16913272.html

相关文章

  • 2022.11.21
    咕了两天blog了,原因是都在颓废。P5410是\(Z\)函数的板子!它与\(KMP\)的思想差不多,同时我认为它更接近\(manacher\),都是由之前的转到当前的,再进行总复杂度\(\Thet......
  • 11-21 日鲜花 - Edit
    <metahttp-equiv="refresh"content="3;url=https://www.luogu.com.cn/blog/Junko-Youmu/e-d-i-t">这东西居然可以在博客园后台预览一个网页?厉害。原文:https://www.lu......
  • 11.21 模拟赛题解
    \(\textdistance\)简要题意给定一棵\(n\)个结点的无根树,每条边有一个边权,询问以哪一个点作为根时,到其他所有节点的距离之和最大。距离的定义为到该点最短路径上的边权......
  • DTOJ 2022-11-21 测试 题解
    测试成果非常寄35+56+0+8=99基本上把能犯的错误都犯了T1记得dp数组初始化\(-\infty\)!!!!T2记得认真暴搜,不要乱记录访问状态T3记得把调试删掉!!!!!T4记得开longlong......
  • AtCoder 题解集
    虽然暂时不知道会不会从XCPC中退役,但还是想把这个题解集给维护下去。\(created\;at\;2022/6/24\;by\;Roshin\)目录AGCARCABCABC138F.Coincidence(结论,数位DP)AB......
  • ZR2448 题解
    题意给定一个长度为\(n\)的匹配的括号序列\(s\)。给出\(q\)组询问,每组询问形如:光标从\(s\)的第\(a\)个字符出发,使用一下三种操作:将光标移到左边的字符。将光......
  • [题解] CF1149D Abandoning Roads
    难得自己想出来一道3000分的题,虽然说考试的时候打挂了...首先先对较小的边缩点,然后求连通块内的最短路。显然,连通块内其实想怎么走就怎么走,但不能走较大的边。然后不同......
  • 11.21.3
    #include<stdio.h>#include<math.h>intmain(){ inti; for(i=10;i<1000;i++) {if(i>=10&&i<100&&pow(i%10,3)+pow(i/10,3)==i)printf("%d ",i); if(i>=100&&i<100......
  • 11.21.3
    #include<stdio.h>intji(inta[]);intmain(){ inta[4],b[3],c[3],d[3],e[3]; inti; for(i=0;i<4;i++) scanf("%d",&a[i]); b[0]=a[0];b[1]=a[1];b[2]=a[2]; c[......
  • 20221118-Python-初始函数
    1.函数的定义    2.函数的参数:    3.函数的返回值:    4.可变长度参数与任意参数 ......