2019/4/1 奇奇怪怪的笔记

整理了一些之前没有写过的东西，把它们拼在一起，并没有什么逻辑可言qwq

FWT快速沃尔什变换

\[ FWT(A)=merge(FWT(A0),FWT(A0+A1)) \]

\[ FWT(A)=merge(FWT(A0+A1),FWT(A1)) \]

\[ FWT(A)=merge(FWT(A0+A1),FWT(Ao-A1)) \]

void FWT(int *a,const int n,int type){    for(int i=1;i
    
     <<=1)for(int j=0;j
     
      <<1)for(k=0;k

杜教筛

问题：求\(S(n)=\sum_{i=1}^{n}f(i)\)

考虑：

构造函数\(g(x)\)

\[ \begin{equation} \begin{split} &\sum_{i=1}^{n}(f*g)(i)\\ =&\sum_{d=1}^{n}\sum_{i=1}^{\frac{n}{d}}g(d)f(i)\\ =&\sum_{d=1}^{n}g(d)S(\frac{n}{d})\\ =&g(1)S(n)+\sum_{d=2}^{n}g(d)S(\frac{n}{d}) \end{split} \end{equation} \]

所以：

\[ S(n)=\frac{\sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d)S(\frac{n}{d})}{g(1)} \]

要找到一个使得\(g\)和\(f*g\)的前缀和都很好算的。

实现：将\(S(n)\)存入数组\(⌊\frac{n}{x}⌋\)位，防止冲突

为什么不会冲突呢，考虑\(\frac{n}{i}\)的\(O(\sqrt n)\)个的商，这些商的商，必然属于\(O(\sqrt n)\)个的商中

为什么呢？

假设：\(n=kd+r,r\leq d\\k=le+s,s\leq e\)

那么就有：\(n=(ed)l+sd+r,sd+r\leq ed\)

所以我们其实只访问了\(O(\sqrt n)\)个的\(S(i)\)，把它们都存储在\(⌊\frac{n}{i}⌋\)

这个值其实是满足\([\frac{n}{i}]=x\)的最大\(x\)值，显然是不会冲突的

\[ \mu* 1 = \epsilon\\ \varphi* 1 = id_1\\id_1 * \mu = \varphi \]

\[ ∑_{i=1}^{n}id_2(i)=\frac{n(n+1)(2n+1)}{6} \]

\[ \sum id_3(i)=(\sum id_1 i)^2 \]

typedef pair
    
      pli;const int B = 1664510, S = 1291;int n, T;ll SumPhi[B + 5], ResPhi[S + 5];int SumMu[B + 5], ResMu[S + 5]; namespace Pac{    void init()//初始化：线筛求出前B=n^{3/2}    {        static int cnt, vis[B + 5], prime[B + 5], phi[B + 5], mu[B + 5];        phi[1] = mu[1] = 1;        for (int i = 2; i <= B; i++)        {            if (!vis[i])            {                prime[cnt++] = i;                phi[i] = i - 1;                mu[i] = -1;            }            for (int j = 0, t; j < cnt && (t = i * prime[j]) <= B; j++)            {                vis[t] = 1;                if (i % prime[j] == 0)                {                    phi[t] = phi[i] * prime[j];                    mu[t] = 0;                    break;                }                phi[t] = phi[i] * (prime[j] - 1);                mu[t] = -mu[i];            }        }        for (int i = 1; i <= B; i++)        {            SumPhi[i] = SumPhi[i - 1] + phi[i];            SumMu[i] = SumMu[i - 1] + mu[i];        }    }    bool vis[S + 5];    pli GetSum(const int x) //求和部分    {        if (x <= B) return pli(SumPhi[x], SumMu[x]);        int t = n / x;        if (!vis[t])        {            vis[t] = 1;            ResPhi[t] = ((ll)x + 1) * x / 2;//phi*1=id_1            ResMu[t] = 1;//mu*1=ep            for (uint l = 2, r; l <= x; l = r + 1)            {                pli res = GetSum(x / l);                r = x / (x / l);                ResPhi[t] -= (r - l + 1) * res.first;                ResMu[t] -= (r - l + 1) * res.second;            }        }        return pli(ResPhi[t], ResMu[t]);    }    void work()    {        init();        scanf("%d", &T);        while (T--)        {            scanf("%d", &n);            memset(vis + 1, 0, sizeof(bool) * n / B);            pli ans = GetSum(n);            printf("%lld %d\n", ans.first, ans.second);        }    }}

最小圆覆盖[随机增量法]

随机大法好

只需要确定三个点，答案即为它们的外接圆

每次加点，如果不属于之前的圆，再枚举另外两个点，确定圆即可

看上去是\(O(n^3)\)的，实际期望是\(O(n)\)

#include
    
     #define ll long long#define ld long double#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)>(b)?(b):(a))#define reg registerusing namespace std;const int MN=100005;const ld eps=1e-12;int N;ld R;struct P{    ld x,y;    P(ld _x=0,ld _y=0):x(_x),y(_y){}}a[MN],O;inline P operator + (const P&o,const P&oo){return P(o.x+oo.x,o.y+oo.y);}inline P operator - (const P&o,const P&oo){return P(o.x-oo.x,o.y-oo.y);}inline P operator * (const P&o,const ld k){return P(o.x*k,o.y*k);}inline ld dot(const P&o,const P&oo){return o.x*oo.x+o.y*oo.y;}inline ld len(const P&o){return sqrt(dot(o,o));}inline ld dis(const P&o,const P&oo){return sqrt((o.x-oo.x)*(o.x-oo.x)+(o.y-oo.y)*(o.y-oo.y));}inline ld cross(const P&o,const P&oo){return o.x*oo.y-o.y*oo.x;}inline P Mid(const P&A,const P&B){return P((A.x+B.x)/2,(A.y+B.y)/2);}//中垂线 inline void Vertical(const P&A,const P&B,P&p,P&v){p=Mid(A,B);P tmp=B-A;v.x=-tmp.y,v.y=tmp.x;}//外接圆 /*P=A+(CA x CD)/(CD x AB) AB*/ inline void Circle(const P&A,const P&B,const P&C){    P p,q,v,w;Vertical(A,B,p,v),Vertical(A,C,q,w);    P u=p-q;    ld t=cross(w,u)/cross(v,w);    O=p+v*t,R=dis(O,A); }int main(){    scanf("%d",&N);    reg int i,j,k;    for(i=1;i<=N;++i)scanf("%Lf%Lf",&a[i].x,&a[i].y);    random_shuffle(a+1,a+N);    O=a[1],R=0;    for(i=2;i<=N;++i)if(dis(a[i],O)>R)    {        O=a[i],R=0;        for(j=1;j
     
      R)        {            O=Mid(a[i],a[j]),R=dis(a[i],O);            for(k=1;k
      
       R)Circle(a[i],a[j],a[k]);        }    }    printf("%.10f\n%.10f %.10f",(double)R,(double)O.x,(double)O.y);    return 0;}

MTT(任意模数NTT)

求\(F(x)*G(x) \mod a\)

\(1\leq n,m\leq 10^5,0\leq f_i,g_i\leq10^9,2\leq p\leq 10^9+9\)

法一：

卷积后每一位不超过\(10^{24}\)

考虑对三个模数：\(469762049,998244353,1004535809\)，分别作\(NTT\)，然后采用\(CRT\)合并

这\(3\)个质数的原根均为\(3\)

考虑\(CRT\)合并怎么做

先合并前两个数，再合并后面两个

但是要用快速乘：

inline ll mul(ll a, ll b,const ll p){    static const long double eps = 1e-8;    a = (a % p + p) % p;    b = (b % p + p) % p;    return ((a * b - ll((long double)a / p * b + eps) * p) % p + p) % p;}

完整代码

#include 
    
     using namespace std;#define ll long long#define reg register#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int x=0,f=1;char ch=getchar();    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}    while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}    return x*f;}const int N=1<<20|5,mod[]={469762049,998244353,1004535809},g=3;#define Mul(a,b,p) (1ll*(a)*(b)%(p))inline int fpow(int x,int m,int p){int r=1;for(;m;m>>=1,x=Mul(x,x,p))if(m&1)r=Mul(r,x,p);return r;}int pos[N],MOD,len,di,F[N],G[N];struct Polynomial{    int P,invg,r[N];    void NTT(int *a,int n,int type)    {        reg int i,j,p,k,w,wn,X,Y;        for(i=0;i
     
      0?g:invg,(P-1)/(i<<1),P);            for(p=i<<1,j=0;j
      
       >1]>>1)|((i&1)<<(di-1));    for(i=0;i<3;++i)    {        poly[i].P=mod[i];        poly[i].invg=fpow(g,mod[i]-2,mod[i]);        poly[i].combine(a,b,len);    }    CRT(n+m-1);    return 0;}