YZOJ P4611 区间加多项式(YJC 的数组/多项式?)
时间限制:4444MS 内存限制:1048576KB
难度:\(7.2\)
-
题目描述
由于本题之前被*了,所以现在数据就是随便造的,可能会因为太水又被艹 //给出题人留点面子吧qwq
YJC 在 AK 了一场校内之后,对其中的一题(P2036 「A Simple Data Structure Problem II 」)产生了兴趣。
于是他出了一题加强版(P4316 「ASDSP VII —— YJC树」),然而,他还是觉得这个加强版太简单啦!!!
所以,这次,他不仅把 \(K \leq 5\) 往后面加了三个零变成了 \(K \leq 5000\) ,还对询问做了一点修改!
喜欢差分的 YJC 有一个长度为 \(N\) 的数组 \(c\),初始值都为 \(0\),下标编号为 \(1, 2, \cdots, N\) 。
现在 YJC 忙着 AK CSP-S2019,没空验证数据的正确性,所以只能把这个重任交给了你 —— ******,希望你能写一个程序帮他实现以下的几个操作:
\(opt=1\),给定 \(L, R\),输出 \(\sum\limits_{i=L}^R c_i\) 的值对 \(998244353\) 取模后的结果;
\(opt=0\),给定 \(L, R\) 以及 \(K\) 次多项式 \(f(x)=\sum\limits_{k=0}^K a_kx^k\),对 \(c_L, c_{L+1}, \cdots, c_R\) 分别加上 \(f(1), f(2), \cdots, f(R-L+1)\) 的值。
-
输入格式
第一行两个正整数 \(N, Q\) ,分别表示区间范围 \([1, N]\) 及询问数 \(Q\) 。
接下来,每行(除了每个 \(opt=0\) 操作的下一行)的第一个数 \(opt\) 表示操作类型。
若 \(opt=0\),则接下来有两个正整数 \(L, R\) 表示操作的区间 \([L, R]\)。紧接着下一行的第一个整数 \(K\) 表示多项式的最高次数为 \(K\) ,接下来 \(K+1\) 个整数 \(a_0, a_1, \cdots, a_K\) 分别表示多项式 \(f(x)= \displaystyle\sum\limits_{k=0}^K a_kx^k\) 的系数;
若 \(opt=1\),则接下来有两个正整数 \(L, R\) 表示询问的区间 \([L, R]\)。
因为 YJC 忙着 AK CSP-S2019(之前说过了),所以他一不小心把数据给加密了。
记 \(lastans\) 为上一个 \(opt=1\) 询问输出的答案(没有则为 \(0\)):对于读入的 \(L\) 和 \(R\),\(L \;\mbox{xor} \left(lastans^2\right)\) 及 \(R \;\mbox{xor} \left(lastans^2\right)\) 分别为真实的 \(L\) 和 \(R\);对于读入的 \(a_k \left(0 \leq k \leq K\right)\),\(a_k \;\mbox{xor}\; lastans\) 为真实的 \(a_k\)。\(\mbox{xor}\) 表示二进制下的异或操作。
(友情提示:数据范围保证的是真实的输入数据的范围。)
-
输出格式
对于每个 \(opt=1\) 操作,输出一行一个数表示答案。
-
样例输入
1 2 3 4 5 6 7 8 |
10 5 1 9 9 0 8 9 0 1 1 9 10 0 3 8 2 0 0 0 1 8 11 |
-
样例输出
1 2 3 |
0 1 74 |
-
样例说明
初始 \(c_9\) 为 \(0\) ,输出 \(0\);
对 \([8, 9]\) 加上 \(f(x)=1\) ;
现在 \(c_9\) 为 \(1\) ,输出 \(1\);
\(lastans=1\),真实的 \(L=3 \;\mbox{xor} \left(1^2\right)=2\),\(R=8 \;\mbox{xor} \left(1^2\right)=9\),\(a_0=a_1=a_2=0 \;\mbox{xor}\; 1=1\) ,即对 \([2, 9]\) 加上 \(f(x)=1+x+x^2\) ;
\(lastans=1\),真实的 \(L=8 \;\mbox{xor} \left(1^2\right)=9\),\(R=11 \;\mbox{xor} \left(1^2\right)=10\),即询问 \(c_9+c_{10}\),输出 \(\left(1+1+8+8^2\right)+0=74\)。
-
数据规模与约定
本题采用子任务制,即只有通过了该子任务下的所有测试点,才能得到其相应的分数。
对于所有的测试点,有 \(1 \leq N \leq 10^{18}\),\(0 \leq Q \leq 100000\),\(0 \leq K \leq 5000\);
\(1 \leq L \leq R \leq N\),\(\forall i \in [0, K]: 0 \leq \left|a_i\right| < 998244353\)。
设每个 \(opt=0\) 操作的 \(K\) 分别为 \(k_1, k_2, \cdots, k_s\) ,记 \(tk = \displaystyle\sum\limits_{i=1}^s {\left(k_i+1\right)}\)。
同时记 \(opt=1\) 操作的总次数为 \(tq\) 。
Subtask 1 (\(1pts\))
\(N \leq 10^5\),\(K \leq 0\),\(Q \leq 100000\),\(tk, tq \leq 50500\)。
Subtask 2 (\(2pts\))
\(K \leq 0\),\(Q \leq 100000\),\(tk, tq \leq 50500\)。
Subtask 3 (\(3pts\))
\(N \leq 10^5\),\(K \leq 1\),\(Q \leq 100000\),\(tk \leq 75500\),\(tq \leq 50500\)。
Subtask 4 (\(4pts\))
\(K \leq 1\),\(Q \leq 100000\),\(tk \leq 65000\),\(tq \leq 50550\)。
Subtask 5 (\(5pts\))
\(N \leq 10^5\),\(K \leq 2\),\(Q \leq 100000\),\(tk \leq 84000\),\(tq \leq 50500\)。
Subtask 6 (\(6pts\))
\(K \leq 2\),\(Q \leq 100000\),\(tk \leq 100000\),\(tq \leq 10500\)。
Subtask 7 (\(7pts\))
\(N \leq 10^5\),\(K \leq 5\),\(Q \leq 100000\),\(tk \leq 175785\),\(tq \leq 49884\)。
Subtask 8 (\(8pts\))
\(K \leq 5\),\(Q \leq 80000\),\(tk \leq 110000\),\(tq \leq 80000\)。
Subtask 9 (\(24pts\))
\(K \leq 500\),\(Q \leq 1000\),\(tk \leq 220000\),\(tq \leq 250\)。
Subtask 10 (\(35pts\))
\(K \leq 5000\),\(Q \leq 75\),\(tk \leq 150000\),\(tq \leq 50\)。
Subtask 11 (\(5pts\))
\(K = 5000\),\(Q \leq 50\)。
如果是根据数据范围选择做法的w也卡不了了qaq
区间加多项式 及 区间查询。
本来只有单点查询的,结果被 L****n * 过去了,然后就变成了难受的区间查询)
本来所有的 \(Q\) 都是 \(\leq 50\) 的,结果被 *agoo* * 过去了,然后就变成了难受的 \(Q\) 和 \(K\) 成反比)
如果 \(N, K\) 比较小的话可以考虑离线差分,开多个树状数组维护。但是本题中 \(N, K\) 都较大,并且强制在线,需要另寻出路。
考虑若修改的区间均为 \([1, R]\),那么实际上只需要维护这些多项式对应次数的系数和即可。因为 \(c_i\) 与 \(f(i)\) 对应,所以对于相同的 \(i^k\) 其系数可以合并。
所以可以把 \(c_i\) 看成一个多项式 \(g(x)\) 在 \(x=i\) 处的值,且 \(g(x)\) 的各项系数为这些多项式的对应次数的系数和。
即若要加入一个多项式 \(f(x)\),因为 \(c_i\) 需要加上 \(f(i)\),而 \(c_i = g(i)\),所以直接把 \(g(x)\) 的各项系数加上 \(f(x)\) 的对应次数的系数即可;
若要查询某一个 \(c_i\) 的值,只需要求出 \(g(x)\) 的每项系数然后把 \(x=i\) 带入即可。
由于 \(K \leq 5000\),所以可以开 \(K\) 棵动态开点线段树分别维护每个 \(g(x)\) 的对应项系数,支持区间修改和单点查询即可。
然而现在要修改的区间为 \([L, R]\),即 \(c_i\) 与 \(f\left(i-L+1\right)\) 对应,\(i^k\) 与 \(\left(i-L+1\right)^k\) 不同所以系数无法直接合并。
所以这里有一个简单粗暴办法,可以平移 \(f(x)\) 强行使得 \(c_i\) 与 \(f(i)\) 对应,然后就可以直接合并了。
原本 \(c_i\) 与 \(f\left(i-L+1\right)\) 对应,要使 \(c_i\) 与 \(f(i)\) 对应,所以把 \(f(x)\) 平移成 \(f(x-L+1)\),这样带入 \(x=i\) 是得到的就是 \(f(i-L+1)\) 的值了。
即若 \(f(x) = \displaystyle\sum\limits_{k=0}^K a_kx^k\),那么平移后的 \(h(x) = f(x+c) = \displaystyle\sum\limits_{k=0}^K a_k\left(x+c\right)^k\),其中 \(c=-L+1\) 。
根据二项式定理展开,有 \(h(x) = \displaystyle\sum\limits_{k = 0}^K {{a_k}} \sum\limits_{j = 0}^k {\left( {\begin{array}{*{20}{c}} {k}\\ j \end{array}} \right) {x^j}{c^{k – j}}}\) 。
交换求和次序,有 \(h(x) = \displaystyle\sum\limits_{j = 0}^K {{x^j}\sum\limits_{k = j}^K {{a_k} \left( {\begin{array}{*{20}{c}} {k}\\ j \end{array}} \right) } } {c^{k – j}}\) 。
这样 \(h(x)\) 就可以在 \(O(K^2)\) 的时间复杂度内求出来了。
继续处理,设 \(t=k-j\),则 \(k=t+j\),有 \(h(x) = \displaystyle\sum\limits_{j = 0}^K {{x^j}\sum\limits_{t = 0}^{K – j} {{a_{j+t}} \left( {\begin{array}{*{20}{c}} {j + t}\\ j \end{array}} \right)} } {c^t}\) 。
组合数拆开,有 \(h(x) = \displaystyle\sum\limits_{j = 0}^K {\frac{{{x^j}}}{{j!}}\sum\limits_{t = 0}^{K – j} {{a_{j + t}}\left( {j + t} \right)!} } \frac{{{c^t}}}{{t!}}\) 。
其实已经可以看出来这是一个卷积的形式了。
再做处理,设 \(A_k = a_{K-k}\left(K-k\right)!\),\(B_k = \displaystyle\frac{c^k}{k!}\),则 \(h(x) = \displaystyle\sum\limits_{j = 0}^K {\frac{{{x^j}}}{{j!}}\sum\limits_{t = 0}^{K – j} {{A_{K – j – t}}} {B_t}}\) 。
设 \(g(n) = \displaystyle\sum\limits_{t = 0}^n {{A_{n – t}}} {B_t}\),可以用 NTT(任意模数FFT) 在 \(O(K \log K)\) 的复杂度内求出 \(n=0, 1, \cdots, K\) 时函数的取值。
最后 \(h(x) = \displaystyle\sum\limits_{j = 0}^K {\frac{{{x^j}}}{{j!}} g(K-j)}\) 就可以得到 \(h(x)\) 的各项系数了。
但是上面的方法仅适用于单点查询,区间查询怎么办?
发现每次询问一个点必须要 \(O(\max\{K\} \log n)\) 的复杂度,由于把 \(c_i\) 看成是多项式的单点值这个设定,所以很难在数据结构等方面有其他的突破。
所以可以考虑在多项式等方面做些处理。
只支持单点查询,又要求区间和,所以可以想到维护 \(c\) 的前缀和。
这样加入一个多项式 \(f(x)\),就相当于在 \([L, R]\) 区间加它的前缀多项式 \(h(x)\),在 \((R, N]\) 区间加常数 \(h(R)\) 。
区间查询时只需查询 \(c_R\) 和 \(c_{L-1}\) 两单点值即可。
前缀多项式 \(h(x) = \displaystyle\sum\limits_{j=1}^x f(j)\),即 \(h(x) = \displaystyle\sum\limits_{j=1}^x \sum\limits_{k=0}^K a_kj^k\)。
展开,有 \(h(x) = \cdots\cdots\cdots\) 。
等等,这怎么展开???里面好像有类似于 \(j^k\) (自然数幂和)的东西,这怎么搞?
这里选用伯努利公式:\(\displaystyle\sum\limits_{k=1}^x k^n = 1^n+2^n+\cdots+x^n = \frac{1}{{n + 1}}\mathop \sum \limits_{k = 0}^n \left( {\begin{array}{*{20}{c}} {n + 1}\\ k \end{array}} \right)B_k^ + {x^{n + 1 – k}}\) 。
其中 \(B_k^+\) 为伯努利数的第 \(k\) 项,\(\displaystyle B_0=1,B_1^\pm=\pm\frac{1}{2},B_2=\frac{1}{6},B_3=0,B_4=\frac{1}{30},\cdots\) 。
伯努利数的定义式为 \({B_0} = 1\),\(\displaystyle\sum\limits_{i = 0}^n {B_i} \left( {\begin{array}{*{20}{c}} {n + 1}\\ i \end{array}} \right) = 0\) 。
所以可以得到其递推式为 \(B_0 = 1\),\(B_n = -\displaystyle\frac{1}{{n + 1}}\sum\limits_{i = 0}^{n – 1} {\left( {\begin{array}{*{20}{c}} {n + 1}\\ i \end{array}} \right){B_i}} \) ,可以在 \(O(K^2)\) 的时间复杂度内算出来,或打表 \(O(1)\),或多项式求逆 \(O(K \log K)\)。
然后就可以继续推 \(h(x)\) 了。
交换求和顺序,有 \(h(x) = \displaystyle\sum\limits_{k = 0}^K {{a_k}} \sum\limits_{j = 1}^x {{j^k}} \) 。
应用上面的公式,有 \(h(x) = \displaystyle\sum\limits_{k = 0}^K {{a_k}\frac{1}{{k + 1}}\sum\limits_{j = 0}^k {\left( {\begin{array}{*{20}{c}} {k + 1}\\ j \end{array}} \right)} B_j^ + {x^{k + 1 – j}}} \) 。
换元,设 \(t=k-j\),则 \(j=k-t\),有 \(h(x) = \displaystyle\sum\limits_{k = 0}^K {{a_k}\frac{1}{{k + 1}}\sum\limits_{t = 0}^k {\left( {\begin{array}{*{20}{c}} {k + 1}\\ {k – t} \end{array}} \right)} B_{k – t}^ + {x^{t + 1}}} \) 。
再次交换求和顺序,有 \(h(x) = \displaystyle\sum\limits_{t = 0}^K {{x^{t + 1}}\sum\limits_{k = t}^K {\frac{{{a_k}}}{{k + 1}}\left( {\begin{array}{*{20}{c}} {k + 1}\\ {k – t} \end{array}} \right)} B_{k – t}^ + } \) 。
这样 \(h(x)\) 就可以在 \(O(K^2)\) 的时间复杂度内求出来了。
组合数展开,再整理,有 \(h(x) = \displaystyle\sum\limits_{t = 0}^K {\frac{{{x^{t + 1}}}}{{(t + 1)!}}\sum\limits_{k = t}^K {{a_k}k!\frac{{B_{k – t}^ + }}{{\left( {k – t} \right)!}}} } \) 。
是不是很熟悉?再换元,设 \(j=k-t\),则有 \(h(x) = \displaystyle\sum\limits_{t = 0}^K {\frac{{{x^{t + 1}}}}{{(t + 1)!}}\sum\limits_{j = 0}^{K – t} {{a_{j + t}}\left( {j + t} \right)!\frac{{B_j^ + }}{{j!}}} } \) 。
是不是更熟悉了?设 \(A_k = a_{K-k}\left(K-k\right)!\),\(C_k = \displaystyle\frac{{B_j^ + }}{{j!}}\),则 \(h(x) = \displaystyle\sum\limits_{t = 0}^K {\frac{{{x^{t + 1}}}}{{(t + 1)!}} \sum\limits_{j = 0}^{K – t} A_{K-t-j}C_j }\) 。
设 \(g(n) = \displaystyle\sum\limits_{j = 0}^n {{A_{n – j}}} {C_j}\),可以用 NTT(任意模数FFT) 在 \(O(K \log K)\) 的复杂度内求出 \(n=0, 1, \cdots, K\) 时函数的取值。
最后 \(h(x) = \displaystyle\sum\limits_{t = 0}^K {\frac{{{x^{t + 1}}}}{{(t + 1)!}} g(K-t)}\) 就可以得到 \(h(x)\) 的各项系数了。
一个类似于总结的东西
区间加多项式(基本区间操作):线段树;(标记永久化比打 \(tag\) 时间和空间都小了一半以上)
多项式平移(支持任意区间修改):FFT;
多项式前缀和(支持区间查询):FFT。
所以本题本来应该是 FFT+FFT+线 段树,时间复杂度 \(O(QK \log N + QK \log K)\),常数巨大。
由于后面 \(Q\) 很小,所以直接暴力是能跑过的,然后你就可以 * 标算了)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_)) #define MOD 998244353 typedef long long LLONG; #ifdef ONLINE_JUDGE char __B[1<<15],*__S=__B,*__T=__B; #define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++) #endif template<typename T> inline T getnum() { register char c=0; register bool neg=false; while(!(c>='0' && c<='9')) c=getchar(),neg|=(c=='-'); register T a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return (neg?-1:1)*a; } inline int _pow(register int base,register int b) { register int ans=1; while(b) { if(b&1) ans=(LLONG)ans*base%MOD; base=(LLONG)base*base%MOD; b>>=1; } return ans; } #define _KLIM 5005 int as[_KLIM<<2],ck[_KLIM<<2],bk[_KLIM<<2]; int flip[_KLIM<<2]; inline void FFT(register int len,int c[],bool inverse=false) { register int t=0; for(register int i=0;i<len;i++) if(i<flip[i]) t=c[flip[i]],c[flip[i]]=c[i],c[i]=t; for(register int step=2;step<=len;step<<=1) { register int wn=_pow(3,(MOD-1)/step); if(inverse) wn=_pow(wn,MOD-2); register int hstep=step>>1; static int pw[_KLIM<<2]; pw[0]=1; for(register int k=1;k<=hstep;k++) pw[k]=(LLONG)pw[k-1]*wn%MOD; for(register int k=0;k<len;k+=step) for(register int i=k;i < k+hstep;i++) { register int j=i+hstep; t=(LLONG)c[j]*pw[i-k]%MOD; (c[j]=c[i]-t)<0 ? c[j]+=MOD : 0; (c[i]+=t)>= MOD ? c[i]-=MOD : 0; } } if(inverse && (t=_pow(len,MOD-2))) for(register int i=0;i<len;i++) c[i]=(LLONG)c[i]*t%MOD; } #define _TSIZE 60505050 LLONG N; int sa[_TSIZE],tag[_TSIZE]; int cnt,lson[_TSIZE],rson[_TSIZE]; struct STree { int root; LLONG Qpos,_Qret; inline void _QueryTree(register int o,register LLONG l,register LLONG r) { if(!o) return; if(l==r) { (_Qret+=sa[o])%=MOD; return; } register LLONG mid=(l+r)>>1; if(Qpos<=mid) _QueryTree(lson[o],l,mid); else _QueryTree(rson[o],mid+1,r); (_Qret+=tag[o])%=MOD; } inline int QueryTree(register LLONG pos) { Qpos=pos,_Qret=0,_QueryTree(root,1,N); return _Qret; } LLONG ML,MR,MV; inline void _ModifyTree(int&o,register LLONG l,register LLONG r) { if(!o) o=++cnt; if(ML<=l && MR>=r) { (tag[o]+=MV)%=MOD; sa[o]=(sa[o]+(LLONG)MV*(r-l+1))%MOD; return; } register LLONG mid=(l+r)>>1; if(ML<=mid) _ModifyTree(lson[o],l,mid); if(MR>mid) _ModifyTree(rson[o],mid+1,r); sa[o]=(sa[lson[o]]+sa[rson[o]]+(LLONG)(r-l+1)%MOD*MV)%MOD; } inline void ModifyTree(register LLONG l,register LLONG r,const int&val) { ML=l,MR=r,MV=val,_ModifyTree(root,1,N); } }tree[_KLIM+1]; int a[_KLIM+1]/*,b[_KLIM+1]*/; int fac[_KLIM+1],invfac[_KLIM+1],inv[_KLIM+1]; #define _comb(_a,_b) ((LLONG)fac[_a]*invfac[_b]%MOD*invfac[(_a)-(_b)]%MOD) const int b[]={1,499122177,582309206,0,356317776,0,561941588,0,884371378,0,754079664,0,368802456,0,200132255,0,96258218,0,79468536,0,724062046,0,337530936,0,263497369,0,891442974,0,400439360,0,323464694,0,25729546,0,220380034,0,624704405,0,312840295,0,987929837,0,896661124,0,14388879,0,911592962,0,669337313,0,683154836,0,392843725,0,99293458,0,190389816,0,518692893,0,540325679,0,831605978,0,949418013,0,450258801,0,74202701,0,617479985,0,680307465,0,526899289,0,995024547,0,933931088,0,768270465,0,151128478,0,361433940,0,621592122,0,730321267,0,446209350,0,230983209,0,653763438,0,731480923,0,670399579,0,81508039,0,786114420,0,837638791,0,268610439,0,41230223,0,778594098,0,506763469,0,143605795,0,639564121,0,344575665,0,160184684,0,537712513,0,238359396,0,590590251,0,315925579,0,264090513,0,583175019,0,617562884,0,769739530,0,321271566,0,544580791,0,393744789,0,667239642,0,708869684,0,437639348,0,501613556,0,40135642,0,341781495,0,155819511,0,100447376,0,344281391,0,472318187,0,173755113,0,338763350,0,87836032,0,58293930,0,249943151,0,493771654,0,718908745,0,873471088,0,116384055,0,901707572,0,891386469,0,654198917,0,597845491,0,344475316,0,879405214,0,362449131,0,859912979,0,645872669,0,89729846,0,887797339,0,646408812,0,781543128,0,38884378,0,267025517,0,550420571,0,852039981,0,57175501,0,457450761,0,356476731,0,855363429,0,401000712,0,608421791,0,676402890,0,566804941,0,258833286,0,625562932,0,23967568,0,862392925,0,391948905,0,633543323,0,495930776,0,880258439,0,133455809,0,728554901,0,578850061,0,135490857,0,195593147,0,95934120,0,811835372,0,737728765,0,71509355,0,631291689,0,608817130,0,861201856,0,381526755,0,451808615,0,428357444,0,469712280,0,170046196,0,816815690,0,881933129,0,91349244,0,399070534,0,190323516,0,17959694,0,482812029,0,168915497,0,906459725,0,718232741,0,100073743,0,666526736,0,578717198,0,247119128,0,500701130,0,822738839,0,185515819,0,476733197,0,663380130,0,586018555,0,849039182,0,596962737,0,443653512,0,456462215,0,921712406,0,698805235,0,456521454,0,371232015,0,742082426,0,654798313,0,958448047,0,254943554,0,868332155,0,86522462,0,803322025,0,539960090,0,187000774,0,196045665,0,177935577,0,779938681,0,742619318,0,184581846,0,899583204,0,983979914,0,397711857,0,182382432,0,290044052,0,986948883,0,925950875,0,87276389,0,597764427,0,53260615,0,218915776,0,775353558,0,833130899,0,833079582,0,775575779,0,996252389,0,567080007,0,954291165,0,935697413,0,704213961,0,291945604,0,472425195,0,507287151,0,664794352,0,127304578,0,725434459,0,367827867,0,733083372,0,365726887,0,368355407,0,568678809,0,207574833,0,553626231,0,613436959,0,68826759,0,508722804,0,513553043,0,457023745,0,168908076,0,213816628,0,757471484,0,102144125,0,958052711,0,455432577,0,156861067,0,532729803,0,660107855,0,233769235,0,133508422,0,479701601,0,116293926,0,511949281,0,274324064,0,935910715,0,737246575,0,400852827,0,145470331,0,743825709,0,45366052,0,980700942,0,366748198,0,561377806,0,918261214,0,784717298,0,236601062,0,27482579,0,170322187,0,446741758,0,355711095,0,477557502,0,144446515,0,654214909,0,371250200,0,559916538,0,169771537,0,279330383,0,614233530,0,15850554,0,766736000,0,138100569,0,826314127,0,620309245,0,229185857,0,238498207,0,532831358,0,365305204,0,808388710,0,550001954,0,753672250,0,658502923,0,219782694,0,584533889,0,464247739,0,68074237,0,717568824,0,113342765,0,226539459,0,297611920,0,215883310,0,809623559,0,621140438,0,655528362,0,891026511,0,520390553,0,721615572,0,421077888,0,830629148,0,608707357,0,478301746,0,805541782,0,393015592,0,622871487,0,188574971,0,148437339,0,182984911,0,570607340,0,305076164,0,438358258,0,688822454,0,894337941,0,342894588,0,184413775,0,864861720,0,392810637,0,320580934,0,944092084,0,243054719,0,497026275,0,856160842,0,259000953,0,414423560,0,771576479,0,725868990,0,446785649,0,362965160,0,350760276,0,441768730,0,266148545,0,810382790,0,515407648,0,20947060,0,130189671,0,735010220,0,388831886,0,31654672,0,808617273,0,51447650,0,604407721,0,949155835,0,978577283,0,460456841,0,125133676,0,943827532,0,860169416,0,313137276,0,192738062,0,540665364,0,44285715,0,807488670,0,229657408,0,481992577,0,529295524,0,272632454,0,204081608,0,688574623,0,186514559,0,183345291,0,216140808,0,244171881,0,697295236,0,949067266,0,348299251,0,884914268,0,710932754,0,474280710,0,767801093,0,925384383,0,130449455,0,892207958,0,322294472,0,568702115,0,679450464,0,994399635,0,616016150,0,679027559,0,325111860,0,349344102,0,871955072,0,491620002,0,439258255,0,879085723,0,138002078,0,87505505,0,127595803,0,931010982,0,357392012,0,540603814,0,818321798,0,92285042,0,308416433,0,344674232,0,941270193,0,803966466,0,234222998,0,958356179,0,80072250,0,774139783,0,915389338,0,776548464,0,946606150,0,518873264,0,466888921,0,372097812,0,582137973,0,158192719,0,674809242,0,990230413,0,487379448,0,73993118,0,859644834,0,216059561,0,332668750,0,829378032,0,334988936,0,443467517,0,37209276,0,33130595,0,180883810,0,681107453,0,100868402,0,690511531,0,103242804,0,16838714,0,815407302,0,518029497,0,956091053,0,790529488,0,847851498,0,619043054,0,835590073,0,421027104,0,683864178,0,164756395,0,568929266,0,884373895,0,427525600,0,195261240,0,915022671,0,687213708,0,213332730,0,70010721,0,841024752,0,151970749,0,614262636,0,77581480,0,825303553,0,453989205,0,378602235,0,482761554,0,785170395,0,971069982,0,4259983,0,257726413,0,809720331,0,22945127,0,389161161,0,348979241,0,970006080,0,44197920,0,386046471,0,156386993,0,319522027,0,771403825,0,615379732,0,858862987,0,457983758,0,973958545,0,188824084,0,525595676,0,681854536,0,314538383,0,184353272,0,801261324,0,93435865,0,586067959,0,912016848,0,582834678,0,464483700,0,966182934,0,265882869,0,539834238,0,563177189,0,270247438,0,140881616,0,58606402,0,496716111,0,288726571,0,795785673,0,795453910,0,743241616,0,77415626,0,110799538,0,27839396,0,823583929,0,693195036,0,509944035,0,294083787,0,313239145,0,978817880,0,234637839,0,846321897,0,178525274,0,957041068,0,163180985,0,773400269,0,21093897,0,650032206,0,978045316,0,335560106,0,693278604,0,942767937,0,913367021,0,113039021,0,882368322,0,971623840,0,626948720,0,837279970,0,650756918,0,539790606,0,482999041,0,341529594,0,454572041,0,289219915,0,302979343,0,22986521,0,859726347,0,619682207,0,91596236,0,932867122,0,835105364,0,35775714,0,380388475,0,586923176,0,248188145,0,190477859,0,395252425,0,557578597,0,773703351,0,486221062,0,61496407,0,581022180,0,154327070,0,430152680,0,696817142,0,909632142,0,874362302,0,884825636,0,930171591,0,820138132,0,814217891,0,778099495,0,802022627,0,567790650,0,198620411,0,519855247,0,787228764,0,4055569,0,25895895,0,896046376,0,562096223,0,787685911,0,486374948,0,579136368,0,168650915,0,451601979,0,122793837,0,183627042,0,794175965,0,956248582,0,124106216,0,5374935,0,859124870,0,748096815,0,799176851,0,49545319,0,996846197,0,950639399,0,208819157,0,983027250,0,443110488,0,518356288,0,463646499,0,33025066,0,87148187,0,421840988,0,217926846,0,350957467,0,433815810,0,950105093,0,739484512,0,152990520,0,754569768,0,341793251,0,355171634,0,503301540,0,269338987,0,356569346,0,740085105,0,249605320,0,619356455,0,615005203,0,329554936,0,786581251,0,164893828,0,581603011,0,805794989,0,352664219,0,65510845,0,450738940,0,905271651,0,135537341,0,276769142,0,697055313,0,988905446,0,268129683,0,273775662,0,426351849,0,665592548,0,430692423,0,158373278,0,102533470,0,526148713,0,930777342,0,664675624,0,500334115,0,606613208,0,668554333,0,206727301,0,752138739,0,795119090,0,554730006,0,463944007,0,305223573,0,730539831,0,773361360,0,489340988,0,812644335,0,588405644,0,929481481,0,382418028,0,972522840,0,822079779,0,713147616,0,850508959,0,347782649,0,792499366,0,577880458,0,616626387,0,120940522,0,341926571,0,793280700,0,849756155,0,884705372,0,102537189,0,371369857,0,545784314,0,605924076,0,141661206,0,877226177,0,153596870,0,152843082,0,19356151,0,853026673,0,663431024,0,870099560,0,323398827,0,143931788,0,542850965,0,422602865,0,470534140,0,142352021,0,654983426,0,545718091,0,473302107,0,340680978,0,763883564,0,441857894,0,467681827,0,529713495,0,995858564,0,803214931,0,332469407,0,32843876,0,978813718,0,724593061,0,306503068,0,70495149,0,1778632,0,986468830,0,891063608,0,218762826,0,797755945,0,456309620,0,850402220,0,986650208,0,309656779,0,907040085,0,491145541,0,96038441,0,820403104,0,455039934,0,507257201,0,800377205,0,387590781,0,358110748,0,300047853,0,61557920,0,780209964,0,48499284,0,476052630,0,169722896,0,29133252,0,718677313,0,191836413,0,455415178,0,756927603,0,560528467,0,809655176,0,389329458,0,845133852,0,945069496,0,177480049,0,926929322,0,534693701,0,143646352,0,248349706,0,993092245,0,224155701,0,233834557,0,733219808,0,54806946,0,807928753,0,31475888,0,483825390,0,768298557,0,859109816,0,148599176,0,687364431,0,518746401,0,590105501,0,403221454,0,126450020,0,323548467,0,104649780,0,591319939,0,134780565,0,751231034,0,576512669,0,817023894,0,439973435,0,863738629,0,933983299,0,290850269,0,86749942,0,544524051,0,199082745,0,516643580,0,443314455,0,421055690,0,499321657,0,644004285,0,152566883,0,22165823,0,115449184,0,720357903,0,131964910,0,943080496,0,177892511,0,799588495,0,368489019,0,474768270,0,480542838,0,558701206,0,677956516,0,122374820,0,233454490,0,512448909,0,386919538,0,84928709,0,303231142,0,850806365,0,434110398,0,76637467,0,808009110,0,9530651,0,306175974,0,753852689,0,480317201,0,413730177,0,129696492,0,699351610,0,824701072,0,278940582,0,842983906,0,407527483,0,506225191,0,236863212,0,80657498,0,410006734,0,138088756,0,817057660,0,576270925,0,650760784,0,438962820,0,637832297,0,367388075,0,996127515,0,492978764,0,55065006,0,641684019,0,567909167,0,962902850,0,617901957,0,857259298,0,534347668,0,916316104,0,349843574,0,137649706,0,20630543,0,67156841,0,214437004,0,499040178,0,934232090,0,35379096,0,572598952,0,229118216,0,131029159,0,486708239,0,139963183,0,467417544,0,771833332,0,400781518,0,51690437,0,629350687,0,980540762,0,65855877,0,183440749,0,716569980,0,450146648,0,349522972,0,335992316,0,543428316,0,70867213,0,755342379,0,800755850,0,404399494,0,485598308,0,400748525,0,116858087,0,205765305,0,276298999,0,765854738,0,889072299,0,221315121,0,316756058,0,869923054,0,614808663,0,726711333,0,281682912,0,670230365,0,780702193,0,50999793,0,191778451,0,284687370,0,864232874,0,881454389,0,90590999,0,963387696,0,44213636,0,194917249,0,580643663,0,134815314,0,58129930,0,352289561,0,706352327,0,118864383,0,139804425,0,619802312,0,259721693,0,101150064,0,364273321,0,36922690,0,833054422,0,697020263,0,452847904,0,650967871,0,513085125,0,325386463,0,655328972,0,385636183,0,663108865,0,539533571,0,311475259,0,586591863,0,143162116,0,757631852,0,600864627,0,826850425,0,426743509,0,926273374,0,576839702,0,170696599,0,39904698,0,625801811,0,405482858,0,539400786,0,91545640,0,126442680,0,82408246,0,716473106,0,824184396,0,838605148,0,652890195,0,266336757,0,333469366,0,628661927,0,775636277,0,171807749,0,116876123,0,318026282,0,824048154,0,909704716,0,510441390,0,832668027,0,99484514,0,927462897,0,326628065,0,784561982,0,104763983,0,672152316,0,644782062,0,722782805,0,335612462,0,763815132,0,323713552,0,365923658,0,960319260,0,236825282,0,120954635,0,518281261,0,785740722,0,73666111,0,245289078,0,962156542,0,417441608,0,278386407,0,156747867,0,922971979,0,938275635,0,584107975,0,440781250,0,485293734,0,111139147,0,563427079,0,194049937,0,349224458,0,440536765,0,585862607,0,392165410,0,759999422,0,896871616,0,665913979,0,73057253,0,508076478,0,167768935,0,936618366,0,231957667,0,724980879,0,901979218,0,829938211,0,271907458,0,379210986,0,224759882,0,776010478,0,887795253,0,798962478,0,425233378,0,332378494,0,638182619,0,283094975,0,254480539,0,583822639,0,982433090,0,729938625,0,790840101,0,691161737,0,728435964,0,148282798,0,224387755,0,757754310,0,442879061,0,87294633,0,617587003,0,382532774,0,755756554,0,739211663,0,798841206,0,591776736,0,539182157,0,967271632,0,679427348,0,663906295,0,331665157,0,406345655,0,783058030,0,706656468,0,580219600,0,357581143,0,719307905,0,565358949,0,180404473,0,17823622,0,985601806,0,729139577,0,964814268,0,468233811,0,388049696,0,142770505,0,806711188,0,944384123,0,542238146,0,750921108,0,935462677,0,308901587,0,460689853,0,165685151,0,645432194,0,509247106,0,607013444,0,508320788,0,357760301,0,876731241,0,162689822,0,933244465,0,214643981,0,90581890,0,823113178,0,428613756,0,844347683,0,637752001,0,719343429,0,829300366,0,251988741,0,715336996,0,858409077,0,126858588,0,435570037,0,656543067,0,392704259,0,253280424,0,580833436,0,82537263,0,98094898,0,415339118,0,558086771,0,813841922,0,838287517,0,274204965,0,719005496,0,639140935,0,25533995,0,513937385,0,317921148,0,775167587,0,704841814,0,676005879,0,4762107,0,613394640,0,183436741,0,642711931,0,596179648,0,28314500,0,561230439,0,964021929,0,336812459,0,465962095,0,796622880,0,845747354,0,315455104,0,901470012,0,283051371,0,180164058,0,678274565,0,760460391,0,401569153,0,966872692,0,703288751,0,9662855,0,223680397,0,162521126,0,970619268,0,142136308,0,292078962,0,184852774,0,780444446,0,951430008,0,537239991,0,749287426,0,280668398,0,203995674,0,179216098,0,150686930,0,847494390,0,662248747,0,652107245,0,579491881,0,704523616,0,986641176,0,618208533,0,24013195,0,844185784,0,764165618,0,673232055,0,102677313,0,968294148,0,742463010,0,329807360,0,669681937,0,871636154,0,245441347,0,908279295,0,357177789,0,149742658,0,690022373,0,686685816,0,385796980,0,775110235,0,621236805,0,295006169,0,895364534,0,151586712,0,175712256,0,334654981,0,971025282,0,696510514,0,32468020,0,648430234,0,672199634,0,249902725,0,400412825,0,862493505,0,343078188,0,49904601,0,712579161,0,178899489,0,243098010,0,683351056,0,531264900,0,507091553,0,960331886,0,13308336,0,493042743,0,62213932,0,934360835,0,592084340,0,333151143,0,82969006,0,872506901,0,167725389,0,115504394,0,615494306,0,520533967,0,925766057,0,689397422,0,804478333,0,522290706,0,570571109,0,72678788,0,854754477,0,130363527,0,750692983,0,310175879,0,538320348,0,348361774,0,810254448,0,407942753,0,542698397,0,512667745,0,217274768,0,764454253,0,942941327,0,248345877,0,843675629,0,179807971,0,795056158,0,79797637,0,344521078,0,88834585,0,723670734,0,699685640,0,578869441,0,341579913,0,99662021,0,868873939,0,434461297,0,124889182,0,309332439,0,535791403,0,96277082,0,780597322,0,746405137,0,427919786,0,770964343,0,279370951,0,217372293,0,934234256,0,68977026,0,193858099,0,473273837,0,420078952,0,748700215,0,909315499,0,829645380,0,184134940,0,573239132,0,552035008,0,932413250,0,661027890,0,46077710,0,289902639,0,958870586,0,745269320,0,361440155,0,7748120,0,150232744,0,361006841,0,341441490,0,77055663,0,158952387,0,816576437,0,694677914,0,321664902,0,801665028,0,863233669,0,216890730,0,418834181,0,40772323,0,198868595,0,296716382,0,227381735,0,60883025,0,910037622,0,941472291,0,961203231,0,10146478,0,285921762,0,306805828,0,68910106,0,742664957,0,580073615,0,389603141,0,650580864,0,46033334,0,763331711,0,478215901,0,277748517,0,908284287,0,848221758,0,620967140,0,158604763,0,893869205,0,412118959,0,276163428,0,54028506,0,191607386,0,707325315,0,625312692,0,408876433,0,870186688,0,103881849,0,617356748,0,696235463,0,136169578,0,806157139,0,99695162,0,526327854,0,859645148,0,320529230,0,99382269,0,993770424,0,857265587,0,20623279,0,427926292,0,327435059,0,393379297,0,415280855,0,87151147,0,316060324,0,486233732,0,472193713,0,86006865,0,918959531,0,866184433,0,397662022,0,826455188,0,993274378,0,903968701,0,2003336,0,190827674,0,142322731,0,508802088,0,600802874,0,986292411,0,813576417,0,509488188,0,375350928,0,230164815,0,16141753,0,140017452,0,600331647,0,773311722,0,244043458,0,854643850,0,683789445,0,763332865,0,892105410,0,472648772,0,845346453,0,212857021,0,168975826,0,653966527,0,265198227,0,183935915,0,472767606,0,127465043,0,420245985,0,239985568,0,448305457,0,819947825,0,814785328,0,939815295,0,405678835,0,220027098,0,894464127,0,36941778,0,54442779,0,362108146,0,587122980,0,250896390,0,673977344,0,18657528,0,743952582,0,181049186,0,193852029,0,108875696,0,947406456,0,312818365,0,670069771,0,436014323,0,289158839,0,434287964,0,387474149,0,314636895,0,310863335,0,469632561,0,3891847,0,581153295,0,177272367,0,524631290,0,532085625,0,102752469,0,877380657,0,751725276,0,388593382,0,621463050,0,896920092,0,229338430,0,823956312,0,144852803,0,325899292,0,960240182,0,342062271,0,4020493,0,630723320,0,486295440,0,191742873,0,767255676,0,429958275,0,437819496,0,642697305,0,111205879,0,856009642,0,404821622,0,778637922,0,953241017,0,272082018,0,932035476,0,483059641,0,981700981,0,209285296,0,431980851,0,937682440,0,698166142,0,114737134,0,336888929,0,751669222,0,786593389,0,960973370,0,421865020,0,931545061,0,519391445,0,248069030,0,76343900,0,521922868,0,818513420,0,752160234,0,476136973,0,955411899,0,72151646,0,799074020,0,800878326,0,237514556,0,965234192,0,555520753,0,631499800,0,138555926,0,167557166,0,930393620,0,371558446,0,70547898,0,368097615,0,906762252,0,539869015,0,428624284,0,123429691,0,299183214,0,651907048,0,626715114,0,327925748,0,20544980,0,545639512,0,598228804,0,552946956,0,537512472,0,645399778,0,291586005,0,372567440,0,315252199,0,89341654,0,744116158,0,365560811,0,780536776,0,495309940,0,524856164,0,580230488,0,180653192,0,854819252,0,542367589,0,989178351,0,528828481,0,243204478,0,994619102,0,724915650,0,418392856,0,117025617,0,739951961,0,667116160,0,618612566,0,764028455,0,681692571,0,203043967,0,360038334,0,98064242,0,199839622,0,137351842,0,158365126,0,490418140,0,430074946,0,737093763,0,25313438,0,155699650,0,124101623,0,852993487,0,631142773,0,473584131,0,533040945,0,372291130,0,656963035,0,831056036,0,320713394,0,69617375,0,406861626,0,44737751,0,841226757,0,575347478,0,776702398,0,614170935,0,697293671,0,442871786,0,609475145,0,376212185,0,151093070,0,64505804,0,115309501,0,205003319,0,667897251,0,501355957,0,948406187,0,597095531,0,487255077,0,538590290,0,415500364,0,27688061,0,304124105,0,538825502,0,882108357,0,343228091,0,753214270,0,53193355,0,207538623,0,532089872,0,684093421,0,705989935,0,672021672,0,428821830,0,940320247,0,788092135,0,415126971,0,132189442,0,933969654,0,921874029,0,203725646,0,179512515,0,840900163,0,255651318,0,251794775,0,123162573,0,541124003,0,805138173,0,561326086,0,661803938,0,113002478,0,87353334,0,327058751,0,800947765,0,586029283,0,766449529,0,765196822,0,803473914,0,463126512,0,988492697,0,205060345,0,32578446,0,697728429,0,54573710,0,742993483,0,397278544,0,260265175,0,893516893,0,938693779,0,658270546,0,561566832,0,443007940,0,509741006,0,599921195,0,30685511,0,514197998,0,281595346,0,322037160,0,351287759,0,471374808,0,863442733,0,685758811,0,742924902,0,331832276,0,441535665,0,112676726,0,727907345,0,651076601,0,968399929,0,700092100,0,399214599,0,829967063,0,426191404,0,844183235,0,720333610,0,569722685,0,142530475,0,711021729,0,866154380,0,322499248,0,625497927,0,342180303,0,946676643,0,597678234,0,724826505,0,156921088,0,403776345,0,626131718,0,413202623,0,344891016,0,804356801,0,238731858,0,340502391,0,939023504,0,231339502,0,220278886,0,36687619,0,179824110,0,320967705,0,805980553,0,351232305,0,901690700,0,897513831,0,940989396,0,384802847,0,404394372,0,645587134,0,986666879,0,290689639,0,919235659,0,994506536,0,973444148,0,172459853,0,975228459,0,762162513,0,864203415,0,96740937,0,890110085,0,15358380,0,480115435,0,914923499,0,490572245,0,859532829,0,449052935,0,510560582,0,583092734,0,256295976,0,313115365,0,546331283,0,503371725,0,343066022,0,453424290,0,148814174,0,321051335,0,415642474,0,878886091,0,409702287,0,134502242,0,355211510,0,685660986,0,331786309,0,543372976,0,198897236,0,40357431,0,861353130,0,725265312,0,659733900,0,930480603,0,685772793,0,694977696,0,739542277,0,60593658,0,709731239,0,260756653,0,522693479,0,110565012,0,994886701,0,204697395,0,655186689,0,750249888,0,375295855,0,496207366,0,850516104,0,89686142,0,218966621,0,310796055,0,806437566,0,990207498,0,3382341,0,816212796,0,893187604,0,736943797,0,728279808,0,879598497,0,599699388,0,441126875,0,15009896,0,489688864,0,209765290,0,526191499,0,509015966,0,660151195,0,678382255,0,979941559,0,957768227,0,301846173,0,153520943,0,140365744,0,40695156,0,78394955,0,865821009,0,506262989,0,661383387,0,730724475,0,8361808,0,5476330,0,616160473,0,106391804,0,276743729,0,36038382,0,480761605,0,142601478,0,401149786,0,908540893,0,2673459,0,742976242,0,238550003,0,886166412,0,970934950,0,593472443,0,326136839,0,252711857,0,885158304,0,115632531,0,206896450,0,66262581,0,109766115,0,58921814,0,376831948,0,153658938,0,825473092,0,753453983,0,377434778,0,740249834,0,71929551,0,96925457,0,187810126,0,660141794,0,210292651,0,26858809,0,195252074,0,771881396,0,525179929,0,103313093,0,646209551,0,358782484,0,466229378,0,712567196,0,286460847,0,820918511,0,410397338,0,236357973,0,258559770,0,850441744,0,51754415,0,763456475,0,135657783,0,564566053,0,585901938,0,810772405,0,188274625,0,969872690,0,333877923,0,859336932,0,673352108,0,521076166,0,421027143,0,51458409,0,178291495,0,218327407,0,664324112,0,863065640,0,62874676,0,802938087,0,331912861,0,812875717,0,122311839,0,260857768,0,541997828,0,259477627,0,690924174,0,460668446,0,452037121,0,351992557,0,870557195,0,232821036,0,860562335,0,272487044,0,532827774,0,826412477,0,699235301,0,67606492,0,211388894,0,113165872,0,972730725,0,596423963,0,41717557,0,978381496,0,402983890,0,774436190,0,44108128,0,715227089,0,734762805,0,724379247,0,627925941,0,532471157,0,486258759,0,434959047,0,54508296,0,650161906,0,385073874,0,152610041,0,651605116,0,528525323,0,129480981,0,902327165,0,483167755,0,993570823,0,216756432,0,400445123,0,576825780,0,428207392,0,11522697,0,329470988,0,889372398,0,591142789,0,951236684,0,178173458,0,558059499,0,63660273,0,811686583,0,743382841,0,956424614,0,237791739,0,516040881,0,312175830,0,779557748,0,743632065,0,934045349,0,831655058,0,539597725,0,575752381,0,597353883,0,262227105,0,450419128,0,854798733,0,430812165,0,601778852,0,174341683,0,691741755,0,121530518,0,15710310,0,479543866,0,648012012,0,695698603,0,202342676,0,174045209,0,637022749,0,290738307,0,803881584,0,336178340,0,902790641,0,255365503,0,92827437,0,165020987,0,313879897,0,618665528,0,228123435,0,499840700,0,980981918,0,937628532,0,843177723,0,332537600,0,760539479,0,676598507,0,743240198,0,770158484,0,610681401,0,4203272,0,283185366,0,778452883,0,895453758,0,473250861,0,647268189,0,748930870,0,738821058,0,625415580,0,93114746,0,525449131,0,813668714,0,660857125,0,135785766,0,283118454,0,930487167,0,988303036,0,799341976,0,251135024,0,424849656,0,461901487,0,310664696,0,836180263,0,900784815,0,559322686,0,833282955,0,244290671,0,888152162,0,557752448,0,677281469,0,888544573,0,585922702,0,613327097,0,647548599,0,375966169,0,472918850,0,348471424,0,707507358,0,336798934,0,677612755,0,746022501,0,495133101,0,438709344,0,618528593,0,932914627,0,908496154,0,554053100,0,845714679,0,957495799,0,639847559,0,930108129,0,412960288,0,196626442,0,492444996,0,15696788,0,340930289,0,185093381,0,886391720,0,164414002,0,395528212,0,266909676,0,412932892,0,130670627,0,388942148,0,571290287,0,171167367,0,268157461,0,500209618,0,10010868,0,670852515,0,742829662,0,457664672,0,930999673,0,973926507,0,665374397,0,637834250,0,373600574,0,694862235,0,606927492,0,17280569,0,851186406,0,952966358,0,797413593,0,763781342,0,798143923,0,140537761,0,956784028,0,845570681,0,557996575,0,734047462,0,467829991,0,10515114,0,264459920,0,685216073,0,294187896,0,722495423,0,985612712,0,359674968,0,949034832,0,239665566,0,264495294,0,913364623,0,413076086,0,183142921,0,854265669,0,201124829,0,733342502,0,853765315,0,235866532,0,211584322,0,903286068,0,345332378,0,400200846,0,318537721,0,375265395,0,159873255,0,239267364,0,733418675,0,749516515,0,632421673,0,982109361,0,212510130,0,423832901,0,309966534,0,228898458,0,501817806,0,181353916,0,489202425,0,353488245,0,42396227,0,823945638,0,407327324,0,754908613,0,448025321,0,970356518,0,754485597,0,519319962,0,868956261,0,638172763,0,383052275,0,184357079,0,987919116,0,887833333,0,129750234,0,374798597,0,593829341,0,829265451,0,849047678,0,579333179,0,8641180,0,557974193,0,993202860,0,752052043,0,166437651,0,701169185,0,892141580,0,41091815,0,175255254,0,132787042,0,680528024,0,653181793,0,655703057,0,432538897,0,581458169,0,359084390,0,392735786,0,61672431,0,124612121,0,85193656,0,674625860,0,719456169,0,79768277,0,661510506,0,501764936,0,399046377,0,102564796,0,208182869,0,84616635,0,565209423,0,267673227,0,720322061,0,639016392,0,142149966,0,369924050,0,442214601,0,818068252,0,788230858,0,583283806,0,230623238,0,556705818,0,268150262,0,433777104,0,165892649,0,894543803,0,214109881,0,935001764,0,703921911,0,515536765,0,539148479,0,55891576,0,599743314,0,749406585,0,790811868,0,936801773,0,472163147,0,296945719,0,720425466,0,248834722,0,985822192,0,61275771,0,447390225,0,533700356,0,606345191,0,295630739,0,981458901,0,702755059,0,309847082,0,957700802,0,871017567,0,170387705,0,956834465,0,315469362,0,921769256,0,739168857,0,463787711,0,191086336,0,416097072,0,624502308,0,329262236,0,46313517,0,899908153,0,335038863,0,323498174,0,491411218,0,932283103,0,596417931,0,226085327,0,220993804,0,158033810,0,380942013,0,752672940,0,252005783,0,983772205,0,115523810,0,535398078,0,185463417,0,58539110,0,229050477,0,837384936,0,118551745,0,151921045,0,422063841,0,676122385,0,116800094,0,943859154,0,750263669,0,136461843,0,174998144,0,196671997,0,51084272,0,532862111,0,326534816,0,625785419,0,248133707,0,478126696,0,312558902,0,792411572,0,31700116,0,943605363,0,464365217,0,10512641,0,519089826,0,505521773,0,287177986,0,856186482,0,278638892,0,321302620,0,440431060,0,765384925,0,411754690,0,635798511,0,306547953,0,505780511,0,311937934,0,80456676,0,720716244,0,717244923,0,208722168,0,283195246,0,500521424,0,367226629,0,594010604,0,972427447,0,820381129,0,538244238,0,985775568,0,45387016,0,916332087,0,515030507,0,418989053,0,532915080,0,106126335,0,128868255,0,785241129,0,905367801,0,793652052,0,854016940,0,108083444,0,352549948,0,239517142,0,407709460,0,933553569,0,674732950,0,658058153,0,498659300,0,171946699,0,257129426,0,45522184,0,279129001,0,729335200,0,359083693,0,366905491,0,618205151,0,60325128,0,93177503,0,19020873,0,293068623,0,948387146,0,988541728,0,277145961,0,785380841,0,468276883,0,784678111,0,136103490,0,759506890,0,232982593,0,346911370,0,668037761,0,811960575,0,632438626,0,349829201,0,435095505,0,154058706,0,363800774,0,231509258,0,247341618,0,433107492,0,873793001,0,390201804,0,137834431,0,25995074,0,554135348,0,430315685,0,555792624,0,370690066,0,729123931,0,190650055,0,251938091,0,661922579,0,81416391,0,961133246,0,834391545,0,885376357,0,129282269,0,386675324,0,824529720,0,687782590,0,829912234,0,732136034,0,201483219,0,786746332,0,969578090,0,327510970,0,91735194,0,957984961,0,466518052,0,989942844,0,817210532,0,47764702,0,523018592,0,826309325,0,313027371,0,854895558,0,413322602,0,176203638,0,469098261,0,24830538,0,175811076,0,941559013,0,56514066,0,300508389,0,815193018,0,269585421,0,212493146,0,142467091,0,816984845,0,283593013,0,765689488,0,853833969,0,308262808,0,661222332,0,301868933,0,31624940,0,374302644,0,877831522,0,87610542,0,499281158,0,184044700,0,660236459,0,304921259,0,701997781,0,40565917,0,193285310,0,506585062,0,136308724,0,574945932,0,79914452,0,457926626,0,665370309,0,570933432,0,389841464,0,33744572,0,974146004,0,670873880,0,983733927,0,457582049,0,383415995,0,997458012,0,489581603,0,600898106,0,207768872,0,315730860,0,483148287,0,680442604,0,30500403,0,592736547,0,786759958,0,463324686,0,179222151,0,381956367,0,779211294,0,620862850,0,93493654,0,690396290,0,346048773,0,703248230,0,195645375,0,116137406,0,43514692,0,870217286,0,152735205,0,127519558,0,570678799,0,468896266,0,171411570,0,202740566,0,130046160,0,382742208,0,79499046,0,243884499,0,40186641,0,300160184,0,322706666,0,430490536,0,675156151,0,133973577,0,81352479,0,531232912,0,721781465,0,839111667,0,729623930,0,538322390,0,264306824,0,334585580,0,386680389,0,934368297,0,934892963,0,791873445,0,786158747,0,682220755,0,50644388,0,788926282,0,368653542,0,83963221,0,226576826,0,716993316,0,815889536,0,526855906,0,817685359,0,162317769,0,966471620,0,989587545,0,632481149,0,970080992,0,812764095,0,912486239,0,716589985,0,734599716,0,75645996,0,262346902,0,749704557,0,76804041,0,388374822,0,192008500,0,400033542,0,878583557,0,207064909,0,67790557,0,837190910,0,477748545,0,281821361,0,363607073,0,901566034,0,246953304,0,624816203,0,270091649,0,342802637,0,394166824,0,467066779,0,815524218,0,106745787,0,715330918,0,208072652,0,973699448,0,932649691,0,614815683,0,297072297,0,329285140,0,920184688,0,740157304,0,377105711,0,980189511,0,521170933,0,41268300,0,964389056,0,596898753,0,649957131,0,970307172,0,402662647,0,623463366,0,798451374,0,744213701,0,248113425,0,430306842,0,385135798,0,691494278,0,4419089,0,908092201,0,771789602,0,567168566,0,559202615,0,553014618,0,402882374,0,22682458,0,29863405,0,749864576,0,180351122,0,722453335,0,224980995,0,754802385,0,800105582,0,231082597,0,906473190,0,66544301,0,569489340,0,189614299,0,320971179,0,926599147,0,300414550,0,87388715,0,189999640,0,42459307,0,925914826,0,613432325,0,908384991,0,315038232,0,648269545,0,249567844,0,875415369,0,380261317,0,284225660,0,249119126,0,179553551,0,78178835,0,302843479,0,865645093,0,968692675,0,115859151,0,477779604,0,25582418,0,236010824,0,218744137,0,321690983,0,868600781,0,185473670,0,405857491,0,126526691,0,558803570,0,552514739,0,62550222,0,168571224,0,819874732,0,622803422,0,508479684,0,662580890,0,958013088,0,592981364,0,656099050,0,304265450,0,113968594,0,132424737,0,660698853,0,518106846,0,114111548,0,813370427,0,55903735,0,54120816,0,589495298,0,21348548,0,256901737,0,937875887,0,963727611,0,222756833,0,195061081,0,490267631,0,565493442,0,106784262,0,328953565,0,540000260,0,181944670,0,185995689,0,203922740,0,327756824,0,969142282,0,84708054,0,632664220,0,192381829,0,374569489,0,239433752,0,576218684,0,847538372,0}; int main() { //freopen("test.in","r",stdin); invfac[0]=fac[0]=fac[1]=1; for(register int i=2;i<=_KLIM;i++) fac[i]=(LLONG)fac[i-1]*i%MOD; invfac[_KLIM]=_pow(fac[_KLIM],MOD-2); for(register int i=_KLIM-1;i>=1;i--) invfac[i]=(LLONG)invfac[i+1]*(i+1)%MOD; inv[0]=inv[1]=1; for(register int i=2;i<=_KLIM;i++) inv[i]=(LLONG)(MOD-MOD/i)*inv[MOD%i]%MOD; /*b[0]=1; for(register int i=1;i<=_KLIM;i++) { for(register int j=0;j<=i-1;j++) b[i]=(b[i]+(LLONG)b[j]*_comb(i+1,j))%MOD; b[i]=(LLONG)b[i]*(MOD-inv[i+1])%MOD; } b[1]=499122177; for(register int i=0;i<=_KLIM;i++) b[i]=(LLONG)b[i]*invfac[i]%MOD;*/ N=getnum<LLONG>(); register int Q=getnum<int>(); register int MK=0; long long lastans=0; for(register int lp=1;lp<=Q;lp++) { register int opt=getnum<int>(); if(opt==0) { register LLONG L=getnum<LLONG>()^(lastans*lastans); register LLONG R=getnum<LLONG>()^(lastans*lastans); register int K=getnum<int>(); MK=_max(MK,K+1); for(register int i=0;i<=K;i++) a[i]=((getnum<int>()^lastans)+MOD)%MOD; register int len=1,dig=0; while(len<((K+2)<<1)) len<<=1,dig++; for(register int i=0;i<len;i++) flip[i]=(flip[i>>1]>>1)|((i&1)<<(dig-1)), as[i]=bk[i]=ck[i]=0; for(register int k=0;k<=K;k++) as[k]=(LLONG)fac[K-k]*a[K-k]%MOD, bk[k]=b[k]; FFT(len,as),FFT(len,bk); for(register int i=0;i<len;i++) bk[i]=(LLONG)as[i]*bk[i]%MOD; FFT(len,bk,true); a[0]=0; for(register int k=0;k<=K;k++) a[k+1]=(LLONG)bk[K-k]*invfac[k+1]%MOD; K++; for(register int k=0;k<=K;k++) as[k]=(LLONG)fac[K-k]*a[K-k]%MOD; for(register int i=K+1;i<len;i++) as[i]=0; ck[0]=1; for(register int k=1,c=(-L+1)%MOD;k<=K;k++) ck[k]=((LLONG)c*ck[k-1]%MOD+MOD)%MOD; for(register int k=0;k<=K;k++) ck[k]=(LLONG)ck[k]*invfac[k]%MOD; FFT(len,as),FFT(len,ck); for(register int i=0;i<len;i++) ck[i]=(LLONG)as[i]*ck[i]%MOD; FFT(len,ck,true); for(register int k=0;k<=K;k++) as[k]=(LLONG)ck[K-k]*invfac[k]%MOD; for(register int i=0;i<=K;i++) tree[i].ModifyTree(L,R,as[i]); register LLONG xr=R%MOD,ansr=0; for(register int k=0,pwr=1;k<=K;k++,pwr=(LLONG)pwr*xr%MOD) ansr=(ansr+(LLONG)as[k]*pwr)%MOD; if(R+1<=N) tree[0].ModifyTree(R+1,N,(int)ansr); } else { register LLONG L=getnum<LLONG>()^(lastans*lastans); register LLONG R=getnum<LLONG>()^(lastans*lastans); register LLONG xl=(L-1)%MOD,xr=R%MOD,ans=0; for(register int k=0,pwl=1,pwr=1;k<=MK;k++) ans=(ans-(LLONG)tree[k].QueryTree(L-1)*pwl%MOD +(LLONG)tree[k].QueryTree(R)*pwr%MOD +MOD)%MOD, pwl=(LLONG)pwl*xl%MOD,pwr=(LLONG)pwr*xr%MOD; printf("%lld\n",lastans=ans); //lastans=0; } } return 0; } |
I’ll AK IO!!!
IOI