难得没挂分。。。通过卡常水了个$rk1$
$T1$是博弈论，打个$SG$表然后倒没啥扩展就是要写个高精。
$T2$啥都不会暴拆式子交暴力。最开始$OJ$又波动了干掉我$5$分重测就回来了。
$T3$打的$35$暴力然后看着只有$5 \times 10^4$的数据范围蠢蠢欲动于是大力卡常$n^2$多拿了$10$分。
倒也没啥水平就是纯粹想不想写的问题吧。。。谁还不会卡常啊。。。
T1：石子
大意：$m$堆石子，每次可以选一堆，假如剩下$x$个那么可以拿走$d$个要求$d \neq x,d|x$。不能拿的人输。问每堆石子最多$n$个则有多少种先手必胜局面。$n\le 10^{10000},m \le 10^{18}$
博弈论。每堆互不影响。所以考虑每一堆的$SG$异或起来就行。
考虑一堆，打表发现对于一个数$x=a \times 2^b$（$a$是奇数）。则$SG(x)=b$
对于$x=1$显然。
对于一个奇数，它的所有决策都是拿走奇数个，剩余状态是偶数，$SG>0$。$mex$之后可知$SG(x)$当$x$为奇数时为零。
对于一个偶数，它可能的决策是拿走$2^0,2^1,2^2,...,2^b$。（可能最后一项是非法的，当$a=1$的时候）
前面乘上一个奇系数没影响。这样所到达的状态都恰好是$2^0,2^1,2^2...2^b$的倍数。
所对应的$SG$分别是$0,1,2,...,b-1,?$。其中$?$是一个$>b$的数。
所以$SG=b$。归纳得证。
所以同时也就知道了$SG$是$log_2n$级别的。大约是$30000$
然后我们需要知道每种$SG$有多少个数。也就是：有多少奇数，有多少$2$的倍数而不是$4$的倍数。。。说白了就是$lowbit$
只需要每次$a=\lceil \frac{n}{2} \rceil$。然后$n \leftarrow \frac{n}{2}$
这里需要高精除低精是$log_2^2n$的有点大。但是只要顺手写个十亿进制压位常数就除$9$了就没问题了。
然后剩下的就是$30000$个$SG$。讲$m$个这玩意异或起来结果不是$0$的方案数。$FWT$板子。
叠个快速幂。总复杂度$O(\frac{log^2_2n}{9} + log_2nlog(log_2n) + log_2nlog\ m)$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mod 998244353 4 int mo(int x){return x>=mod?x-mod:x;} 5 int qp(int b,int t,int a=1){for(;t;t>>=1,b=1ll*b*b%mod)if(t&1)a=1ll*a*b%mod;return a;} 6 #define S 1<<20 7 int lg,SG[S],ans[S],Ans,n[S],bn,rev[S],len; long long m; char N[S]; 8 void FWT(int*a,int op=1){ 9 for(int i=0;i<len;++i)if(rev[i]>i)swap(a[i],a[rev[i]]); 10 for(int i=1;i<len;i<<=1)for(int j=0;j<len;j+=i<<1) 11 for(int k=j,x,y;k<j+i;++k) 12 x=a[k],y=a[k+i],a[k]=mo(x+y),a[k+i]=mo(x+mod-y); 13 if(op==-1)for(int iv=qp(len,mod-2),i=0;i<len;++i)a[i]=1ll*a[i]*iv%mod; 14 } 15 int main(){ 16 scanf("%s%lld",N,&m); len=strlen(N); reverse(N,N+len); 17 for(int j=len-1;~j;--j)n[j/9+1]=n[j/9+1]*10+N[j]-48; 18 len=(len-1)/9+1; 19 for(lg=0;len;++lg){ 20 SG[lg]=n[1]&1; int x=0; 21 for(int j=len;j;--j)n[j-1]+=(n[j]&1)*1000000000,n[j]>>=1,x=(x*1000000000ll+n[j])%mod; 22 SG[lg]+=x; while(len&&!n[len])len--; 23 } 24 ans[0]=len=1; 25 while(len<=lg)len<<=1; 26 for(int i=1;i<len;++i)rev[i]=rev[i>>1]>>1|(i&1?len>>1:0); 27 FWT(ans);FWT(SG); 28 for(;m;m>>=1){ 29 if(m&1)for(int i=0;i<len;++i)ans[i]=1ll*ans[i]*SG[i]%mod; 30 for(int i=0;i<len;++i)SG[i]=1ll*SG[i]*SG[i]%mod; 31 }FWT(ans,-1); 32 for(int i=1;i<len;++i)Ans=mo(Ans+ans[i]); 33 printf("%d\n",Ans); 34 }
T2：奥术
大意：数串。支持复制一段区间到另一段，询问一个子串，它的所有子串的值的和。$n,Q \le 10^5$
发现答案是关于$1,l,10^r,l\times 10^r$的一次项式的和。线段树维护暴力修改。
然后赋值操作可以可持久化平衡树。需要定期重构。写个毛线。
T3：排列
大意：求所有满足最长上升/下降子串长度$\le 2$的长度介于$[L,R]$之间的排列个数。$R \le 10^6$
首先这差不多是个原题。可以用同样的方法做。只不过最后统计答案的时候稍微改变一下。
当时计数的是对于某个特定长度。换成一个区间后，发现是卷积形式。。。$O(nlogn)$
题解做法是，首先设$f_n$表示长度为$n$的满足条件的排列个数。
发现$W,M$形排列是相对的只要计数其中一种最后再乘$2$即可。（特殊考虑$n=1$）
我们假如只计数$W$形。枚举数字$n$所在的位置，得到$f_n= \sum\limits_{i=1}^{\frac{n}{2}} \binom{n-1}{2i-2} f_{2i-2} f_{n-(2i-1)}$
同理枚举数字$1$的位置，得到$f_n=\sum\limits_{i=1}^{\frac{n}{2}} \binom{n-1}{2i-1} f_{2i-1} f_{n-2i}$
二式相加得到$f_n =\sum\limits_{i=1}^{n} \binom{n-1}{i-1} f_{i-1} f_{n-i}$
拆开组合数得到$\frac{2f_n}{(n-1)!} = \sum\limits_{i=0}^{n-1} \frac{f_i}{i!} \frac{f_{n-i-1}}{(n-i-1)!}$
很像指数型生成函数。但是左边错位了且还有系数。错位可以用导数处理，故得到$2F‘=F^2+1$
$\frac{F‘}{F^2+1}=\frac{1}{2}$
我们有$tan‘(x)=(\frac{sin}{con})‘(x) = \frac{sin^2(x)+cos^2(x)}{cos^2(x)}=1+tan^2(x)$
然后就有设$arctan‘(y)=\frac{1}{1+y^2}$。考虑$y=tan(x)$，定义域仍然是$R$。
所以其实也就是$x$关于$tan(x)$的导数。
所以也就是$tan(x)$关于$x$的导数的倒数。
所以也就是$\frac{1}{1+tan^2(x)}$。代回得到$\frac{1}{1+y^2}$
所以发现原式就是$arctan‘(F(x))$的形式。（复合函数求导）
所以我们得到$arctan‘(F(x))=\frac{1}{2}$。
所以有$arctan(F(x))=\frac{1}{2}x+c$（根据导数还原原函数，然而还原时可能会多出来一个常数，是在求导时消失的常数项）
所以$F(x)=tan(\frac{1}{2}x+c)$
显然有$F(0)=1$。带入得知$c=\frac{\pi}{4}$
$tan(\frac{1}{2}x+\frac{\pi}{4})$
$ = \frac{sin(\frac{1}{2}x+\frac{\pi}{4})}{cos(\frac{1}{2}x+\frac{\pi}{4})}$
$ = \frac{sin(\frac{1}{2}x)+cos(\frac{1}{2}x)}{cos(\frac{1}{2}x)-sin(\frac{1}{2}x)}$
$ = \frac{sin^2(\frac{1}{2}x)+cos^2(\frac{1}{2}x)+2sin(\frac{1}{2}x)cos(\frac{1}{2}x)}{cos^2(\frac{1}{2}x)-sin^2(\frac{1}{2}x)}$
$=\frac{1+sin(x)}{cos(x)}$
然后只需要级数求和。。。
$sin(x)=\sum (-1)^{i-1} \frac{x^{2i-1}}{(2i-1)!}$
$cos(x)=\sum (-1)^i \frac{x^{2i}}{(2i)!}$
然后多项式求逆就没了。$O(nlogn)$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mod 998244353 4 #define S 1<<21 5 int qp(int b,int t,int a=1){for(;t;t>>=1,b=1ll*b*b%mod)if(t&1)a=1ll*a*b%mod;return a;} 6 int mo(int x){return x>=mod?x-mod:x;} 7 int rev[S],a[S],r[S],L,R,len,X[S],fac[S],inv[S],ans; 8 void NTT(int*a,int op=1){ 9 for(int i=0;i<len;++i)if(rev[i]>i)swap(a[i],a[rev[i]]); 10 for(int i=1;i<len;i<<=1)for(int j=0,w=qp(3,(mod-1)/i/2*op+mod-1);j<len;j+=i<<1) 11 for(int k=j,t=1,x,y;k<j+i;++k,t=1ll*t*w%mod) 12 x=a[k],y=1ll*a[k+i]*t%mod,a[k]=mo(x+y),a[k+i]=mo(mod+x-y); 13 if(op==-1)for(int i=0,iv=qp(len,mod-2);i<len;++i)a[i]=1ll*a[i]*iv%mod; 14 } 15 void sat(int x){ 16 len=1;while(len<=x)len<<=1; 17 for(int i=0;i<len;++i)rev[i]=rev[i>>1]>>1|(i&1?len>>1:0); 18 } 19 void Inv(int*a,int n){ 20 static int R[S]; 21 if(n==1){r[0]=qp(a[0],mod-2);return;} 22 Inv(a,n+1>>1); sat(n<<1); 23 for(int i=0;i<len;++i)R[i]=i<n?a[i]:0; 24 NTT(R);NTT(r); for(int i=0;i<len;++i)r[i]=(r[i]+r[i]-R[i]*1ll*r[i]%mod*r[i]%mod+mod)%mod; 25 NTT(r,-1); for(int i=n;i<len;++i)r[i]=0; 26 } 27 int main(){ 28 scanf("%d%d",&L,&R); 29 for(int i=fac[0]=1;i<=R;++i)fac[i]=fac[i-1]*1ll*i%mod; 30 inv[R]=qp(fac[R],mod-2); 31 for(int i=R-1;~i;--i)inv[i]=inv[i+1]*(i+1ll)%mod; 32 for(int i=0;i<=R;i+=2)a[i]=i>>1&1?mod-inv[i]:inv[i]; 33 Inv(a,R+1); sat(R+R); 34 for(int i=0;i<=R;++i)a[i]=0; 35 for(int i=a[0]=1;i<=R;i+=2)a[i]=i>>1&1?mod-inv[i]:inv[i]; 36 NTT(r);NTT(a); for(int i=0;i<len;++i)a[i]=a[i]*1ll*r[i]%mod; NTT(a,-1); 37 for(int i=L;i<=R;++i)ans=(ans+1ll*fac[i]*a[i])%mod; 38 printf("%d\n",ans*2%mod-(L==1)); 39 }
原文：https://www.cnblogs.com/hzoi-DeepinC/p/12838083.html
