金华市东阳市建设局网站,外协机械加工订单,app制作软件官网,成都美食网站设计论文神仙zq发现了${n^2\sqrt n}\over 32$做法 Description 你有三个系数为0,1的多项式f(x),g(x),h(x)求f(g(x)) mod h(x)为方便起见#xff0c;将答案多项式所有系数对2取模输出即可如果f(x)Sigma(Ak * Xk)则f(g(x))Sigma(Ak(g(x))KInput 一共三行#xff0c;每行一个多项式,分别… 神仙zq发现了${n^2\sqrt n}\over 32$做法 Description 你有三个系数为0,1的多项式f(x),g(x),h(x) 求f(g(x)) mod h(x) 为方便起见将答案多项式所有系数对2取模输出即可 如果f(x)Sigma(Ak * Xk) 则f(g(x))Sigma(Ak(g(x))K Input 一共三行每行一个多项式,分别为f,g,h 对于一个多项式描述为n P0,P1...Pn其中Pi为0或1 多项式P(x)P0P1*x....Pn*xn 记n表示多项式最高项的次数,n4000 Output 用同样的格式输出答案多项式 如果答案为0输出0 0 题目分析 陈老师神题x1 观察到这里多项式的所有操作都是在系数$\mod 2$的意义下的因此可以用bitset来加速多项式的一些操作。例如$O(n^2)$实现多项式取模。 1 void mod(poly a, int pos)
2 {
3 for (int ipos; ip; i--)
4 if (a[i]) a ^ c(i-p), a[i] 0; //我第一次居然把标红地方给忘了
5 } 但是如同很多bitset的技巧题一样非常重要的一点是bitset每次整体操作的复杂度是 $O(size)$ 的。 这意味着$Poly\, :O(n), \, Poly\, *:O(n^2)$ 接下去我们从暴力开始谈起。 暴力做法 $O({{n^3}\over 32})$ 第一个需要解决的问题是$f(g(x))$。那么我们只需要对$g(x)$求$k$次幂也即最暴力地k次自乘再将这些结果相加得到多项式$f(g(x))$。至于取模的过程则可以在每次multiply的时候顺带模干净这样最终相加得到的结果就是在模多项式意义下的答案。 1 void mod(poly a, int pos) //pos是a的度数2 {3 for (int ipos; ip; i--)4 if (a[i]) a ^ c(i-p), a[i] 0;5 }6 void mult(poly a, poly b, poly ret) //reta*b7 {8 ret.reset();9 for (int i0; ip; i)
10 if (a[i]) ret ^ bi; //这里就是模拟n^2多项式乘法的过程
11 mod(ret, p1);
12 } 总的代码 1 #includebits/stdc.h2 const int maxn 8035;3 typedef std::bitsetmaxn poly;4 5 int n,m,p;6 poly a,b,c,tmp,cnt;7 8 void input(poly a, int n)9 {
10 scanf(%d,n);
11 for (int i0, x; in; i)
12 {
13 scanf(%d,x);
14 if (x) a.set(i);
15 }
16 }
17 void mod(poly a, int pos)
18 {
19 for (int ipos; ip; i--)
20 if (a[i]) a ^ c(i-p), a[i] 0;
21 }
22 void mult(poly a, poly b, poly ret)
23 {
24 ret.reset();
25 for (int i0; ip; i)
26 if (a[i]) ret ^ bi;
27 mod(ret, p1);
28 }
29 int main()
30 {
31 input(a, n), input(b, m), input(c, p);
32 tmp[0] 1, mod(b, m);
33 for (int i0; in; i)
34 {
35 if (a[i]) cnt ^ tmp;
36 mult(tmp, b, tmp); //复杂度n^3在这里
37 }
38 while (p0!cnt[p]) --p;
39 if (p-1) puts(0 0);
40 else{
41 printf(%d,p);
42 for (int i0; ip; i)
43 printf( %d,cnt[i]?1:0);
44 }
45 return 0;
46 } 对系数按10位分块 $O({{n^3}\over 320})$ 参见法老博客[BITSET 分块] BZOJ5087. polycomp 注md[t]并不一定要等于0.这里的取模多项式最高位对计算无影响。 容易发现这种做法的复杂度的阶仍然是$n^3$. 对$ia\sqrt kb$分块 $O({{n^2\sqrt n}\over 32})$ 233转载于:https://www.cnblogs.com/antiquality/p/10507033.html
