[51nod 1727] 小Q的数列

51nod 1727

思路

啊不想写了粘个标解走人(逃

考虑到是双射,并且在$n>1$时,一组Alice数列每个数全加$1$、Bob数列每个数全减$1$就可以得到一组新的解(从数列的生成函数上可以看出来),所以只用计算本质不同的解,解等价于$(1+x+x^2+\dots +x^{n^2−1})(1+x+x^2+\dots +x^{n^2−1})$的某种因式个数,这种因式满足:系数为非负整数且系数之和为$n$,且乘上一个具有相同性质的因式可以得到原式。

通过观察验证法或不易证得,可以建立如下的dp方程。

设$f_{n,m}$表示一个数列长度为$n$,一个数列长度为$m$,当前可以切分长度为$n$的数列,对应笛卡尔和数列是$n\cdot m$个数的本质不同方案数。

初始状态:$f_{n,1}=1$,显然只有一组本质不同的解$\{1,2,\dots ,n\}\oplus\{0\}$。

状态转移方程:$$f_{n,m}=\sum \limits_{k|n,k<n} f_{m,k}$$ ,相当于将笛卡尔和数列的一部分拆成几个段按照一定规律生成$(xk−1|xn−1)$。$n=1$时,答案为$1$;$n>1$时,所求即$2\cdot f_{n,n}$ 。

如果直接利用递推式,单组询问的计算复杂度为$O(σ(n)τ_3(n))$,其中$τ3(n)=\sum \limits_{d|n}σ(d)$ ,难以在时限内出解,但是可以帮助得到下面的结论。

考虑这个(分圆)多项式和递推方程,如果只计算$f_{n,n}$,可以发现需要计算的$f_{a,b}$ 都满足$a|n$且$b|n$,因此对于一个$n$可以找到这样的二元组组成的偏序关系$S_n$ 。可以发现,对于不同的$n$,有很多偏序关系$S_n$是同构的,例如质数$p$之间的偏序关系$S_p$都是同构的,均为$f(p,p)\to f(p,1)\to f(1,1)$。

这是因为,令$n$的质因子分解里每个质数的指数组成的可重无序集合为 $T_n$,显然,若$T_n=T_m$,那么$S_n$与$S_m$同构。

我们可以预处理出来对于所有每个质数的指数组成的可重无序集合的答案

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define pb push_back
#define MOD 10000000061ll
typedef long long ll;
int pri[1000010], top, cnt[1000010];
bool fl[1000010];
ll ans[1000010], C[110][110], f[110];
std::vector<int> vec[1000010];

void dfs(int x, ll sum, int lst){
    vec[++top].assign(cnt+1, cnt+x);
    for(cnt[x]=1; cnt[x]<=lst; cnt[x]++){
        sum*=pri[x];
        if(sum>1e12) return;
        dfs(x+1, sum, cnt[x]);
    }
}

ll mul(ll x, ll y){return (__int128)x*y%MOD;}

int main(){
    for(int i=2; i<=1000000; i++){
        if(!fl[i]) pri[++pri[0]]=i;
        for(int j=1; j<=pri[0] && i*pri[j]<=1000000; j++){
            fl[i*pri[j]]=true;
            if(i%pri[j]==0) break;
        }
    }
    dfs(1, 1, 1000000);
    C[0][0]=1;
    for(int i=1; i<=100; i++){
        C[i][0]=1;
        for(int j=1; j<=i; j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
    }
    for(int i=1; i<=top; i++){
        int tot=0;
        for(auto j: vec[i]) tot+=j;
        for(int j=0; j<=tot; j++){
            f[j]=1;
            for(auto k: vec[i]) f[j]=mul(f[j], C[k+j-1][j-1]);
        }
        for(int j=0; j<=tot; j++)
            for(int k=0; k<j; k++) f[j]=(f[j]-mul(C[j][k], f[k]))%MOD;
        for(int j=0; j<=tot; j++)
            ans[i]=(ans[i]+mul(f[j], f[j]))%MOD;
        for(int j=0; j<tot; j++)
            ans[i]=(ans[i]+mul(f[j], f[j+1]))%MOD;
        ans[i]=(ans[i]<<1)%MOD; ans[i]=(ans[i]+MOD)%MOD;
    }
    int T; ll N;
    scanf("%d", &T);
    for(int _=1; _<=T; _++){
        scanf("%lld", &N);
        if(N==1){
            printf("Case #%d: 1\n", _);
            continue;
        }
        std::vector<int> now;
        for(int i=1; i<=pri[0]; i++) if(N%pri[i]==0){
            int t=0; 
            while(N%pri[i]==0) N/=pri[i], t++;
            now.pb(t);
        }
        if(N>1) now.pb(1);
        std::sort(now.begin(), now.end(), [](int x, int y){return x>y;});
        int pos=std::lower_bound(vec+1, vec+top+1, now)-vec;
        printf("Case #%d: %lld\n", _, ans[pos]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注