题解 | #Mocha 的手套收藏#

赛时卡常卡了好久。。。

首先考虑枚举多少双手套是用 2 操作分的，可以得到 $answer=\sum\limits_{i=0}^{\frac{n}{2}} \binom n {2i} \times \binom {2i} i$ 。

如果模数是质数就很好做了，但可惜并不一定是。

将两个组合数拆开，得到 $answer=\sum\limits_{i=0}^{\frac{n}{2}} \frac{n!}{(n-2i)!(i!)^2}$ 。

考虑枚举 $i$ 的时候从 $i-1$ 的值推到 $i$ 的值，可以发现是每次乘上若干个数再除以若干个数。

可以用一个权值线段树来维护，线段树的第 $i$ 个位置表示第 $i$ 个质数在这个数分解质因数后的结果里出现了多少次。每个结点维护区间积。

具体乘除的时候将乘除的数分解质因数再在对应的位置修改出现次数即可。需要线性筛预处理每个数分解质因数的结果。

记 $f(n)$ 表示 n 以内质因数个数和，时间复杂度 $\mathcal O(f(n)\log n)$ 。 $f(10^6)$ 大概在 $3\times 10^6$ 左右。

因为常数原因，需要写 zkw 线段树加上一些奇技淫巧来卡常。

因为卡常的原因所以代码有点乱，凑合着看吧：

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int N=1e6+5;
const int M=1e5+5;

int read()
{
    int s=0;
    char c=getchar(),lc='+';
    while (c<'0'||'9'<c) lc=c,c=getchar();
    while ('0'<=c&&c<='9') s=s*10+c-'0',c=getchar();
    return lc=='-'?-s:s;
}
void write(int x)
{
    if (x<0) putchar('-'),x=-x;
    if (x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
void print(int x,char c='\n')
{
    write(x);
    putchar(c);
}
int n,p,ans=0;
inline void add(int &x,int y)
{
    x+=y;
    if (x>=p) x-=p;
}
bool vis[N];
int pr[M],cntp=0;
vector<int>fac[N];
inline int power(long long a,int b)
{
    long long ret=1;
    while (b)
    {
        if (b&1) ret=ret*a%p;
        a=a*a%p;
        b/=2;
    }
    return ret;
}
struct segment_tree
{
    bool vis[M];
    int n,t[(1<<18)+5],val[M],st[M],top;
    vector<int>Pow[M];
    segment_tree():n(1<<17){}
    void add(int x,int y)
    {
        if (!vis[x]) st[++top]=x,vis[x]=1;
        if (y>0)
        {
            val[x]++;
            if (val[x]>(int)Pow[x].size())
            {
                t[n+x-1]=1LL*t[n+x-1]*pr[x]%p;
                Pow[x].push_back(t[n+x-1]);
            }
            else t[n+x-1]=Pow[x][val[x]-1];
        }
        else
        {
            val[x]+=y;
            if (val[x]) t[n+x-1]=Pow[x][val[x]-1];
                   else t[n+x-1]=1;
        }
    }
    void mul(int x,int y)
    {
        if (x<=1) return;
        for (int i:fac[x]) add(i,y);
    }
    void push_up()
    {
        int x;
        while (top)
        {
            x=st[top--];
            vis[x]=0;
            for (x=(n+x-1)/2;x>=32;x/=2) t[x]=1LL*t[x*2]*t[x*2+1]%p;
        }
    }
}t;

signed main()
{
    n=read(),p=read();
    for (int i=2;i<=n;i++)
    {
        if (!vis[i]) pr[++cntp]=i,fac[i].push_back(cntp);
        for (int j=1;j<=cntp;j++)
        {
            if (1LL*pr[j]*i>n) break;
            vis[pr[j]*i]=1;
            fac[i*pr[j]]=fac[i];
            fac[i*pr[j]].push_back(j);
            if (i%pr[j]==0) break;
        }
    }
    for (int i=1;i<=t.n*2;i++) t.t[i]=1;
    for (int i=0;i<=n/2;i++)
    {
        int mul=1;
        for (int j=32;j<64;j++) mul=1LL*mul*t.t[j]%p;
        add(ans,mul);
        if (i==n/2) break;
        t.mul(n-i*2,1);
        t.mul(n-i*2-1,1);
        t.mul(i+1,-2);
        t.push_up();
    }
    print(ans);

    return 0;
}