洛谷5320 [BJOI2019]勘破神机

Luogu

LOJ

分析

先看 $m=2$ 的情况,可以发现 $2\times n$ 的格子的方案数就是斐波那契数列的第 $n+1$ 项。为了方便我们把 $l$ 和 $r$ 加上 $1$ ,这样子就变成了第 $n$ 项。

根据特征方程相关知识可以得到 $f_n=A\alpha^n+B\beta^n$ ,这里的 $A=\frac{1}{\sqrt{5}},B=-\frac{1}{\sqrt{5}},\alpha=\frac{1+\sqrt{5}}{2},\beta=\frac{1-\sqrt{5}}{2}$ 。

然后大力推式子:

$$\displaystyle\begin{aligned}\sum_{n=l}^r{f_n\choose k}&=\frac{1}{k!}\sum_{n=l}^r\sum_{i=0}^k(-1)^{k-i}\begin{bmatrix}k\\i\end{bmatrix}{f_n}^i\\&=\frac{1}{k!}\sum_{n=l}^r\sum_{i=0}^k(-1)^{k-i}\begin{bmatrix}k\\i\end{bmatrix}\left(A\alpha^n+B\beta^n\right)^i\\&=\frac{1}{k!}\sum_{n=l}^r\sum_{i=0}^k(-1)^{k-i}\begin{bmatrix}k\\i\end{bmatrix}\sum_{j=0}^i{i\choose j}A^jB^{i-j}\left(\alpha^j\beta^{i-j}\right)^n\\&=\frac{1}{k!}\sum_{i=0}^k(-1)^{k-i}\begin{bmatrix}k\\i\end{bmatrix}\sum_{j=0}^i{i\choose j}A^jB^{i-j}\sum_{n=l}^r(\alpha^i\beta^{i-j})^n\end{aligned}$$

后面那个东西是一个等比数列可以直接算。那么预处理处第一类斯特林数和组合数就可以 $O(n^2)$ 计算这个式子了。


再看 $m=3$ 的情况 强行二合一差评

可以发现,$n$ 是奇数时答案为 $0$ ,$n$ 为偶数时(令 $g_n$ 表示 $3\times 2n$ 格子的答案)有 $g_n=4g_{n-1}-g_{n-2}$ 。

根据特征方程相关知识可以解得 $g_n=A\alpha^n+B\beta^n$ ,这里的 $A=\frac{3+\sqrt{3}}{6},B=\frac{3-\sqrt{3}}{6},\alpha=2+\sqrt{3},\beta=2-\sqrt{3}$ 。

然后和前面的一样的算。


但是还有一个问题,就是 $3$ 和 $5$ 在模 $\mathbf{998244353}$ 意义下不存在二次剩余。

我们可以考虑扩域,把每个数表示成 $a+b\sqrt{x}$ 的形式,再重载它的运算符即可。它的运算和复数是类似的。

然后就做完了。具体实现及细节见代码。

代码

抄 rqy 代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int K=501+10;
const int mod=998244353;

int S[K][K],C[K][K],fac[K];

inline int qpow(int a,int b) {
    a%=mod; int c=1;
    for (;b;b>>=1,a=a*a%mod) if (b&1) c=c*a%mod;
    return c;
}

template<int w>
struct num { //x+y*sqrt{w}
    int x,y;
    num(int x_=0,int y_=0):x(x_%mod),y(y_%mod) { }
    inline num conj() { return num(x,-y); }
    
    friend num operator +(num a,num b) { return num(a.x+b.x,a.y+b.y); }
    friend num operator -(num a,num b) { return num(a.x-b.x,a.y-b.y); }
    friend num operator *(num a,num b) { return num(a.x*b.x+w*a.y*b.y,a.x*b.y+a.y*b.x); }
    friend num operator /(num a,num b) { return num(a.x*b.x-w*a.y*b.y,a.y*b.x-a.x*b.y)*qpow(b.x*b.x-w*b.y*b.y,mod-2); }
};

template<int w>
inline num<w> qpow(num<w> a,int b) {
    num<w> c=1;
    for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
    return c;
}

template<int w>
inline num<w> solve(num<w> A,num<w> p,num<w> B,num<w> q,int l,int r,int k) {
    ++r;
    num<w> ans=0,pl=qpow(p,l),pr=qpow(p,r),ql=qpow(q,l),qr=qpow(q,r);
    num<w> mpl=1,mpr=1,mp=1,mA=1;
    for (re int i=0;i<=k;++i) {
        num<w> mql=1,mqr=1,mq=1,mB=1;
        for (re int j=0;i+j<=k;++j) {
            num<w> a=mp*mq-1,b=mpr*mqr-mpl*mql;
            num<w> d=!a.x&&!a.y?(r-l)%mod:b/a;
            num<w> now=S[k][i+j]*C[i+j][i]%mod*mA*mB*d;
            ans=ans+now;
            mB=mB*B,mql=mql*ql,mqr=mqr*qr,mq=mq*q;
        }
        mA=mA*A,mpl=mpl*pl,mpr=mpr*pr,mp=mp*p;
    }
    return ans*qpow(fac[k],mod-2);
}

signed main() {
    S[0][0]=C[0][0]=fac[0]=1;
    for (re int i=1;i<K;++i)
        for (re int j=C[i][0]=1;j<=i;++j)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    for (re int i=1;i<K;++i) {
        S[i][0]=-(i-1)*S[i-1][0];
        for (re int j=1;j<=i;++j)
            S[i][j]=(S[i-1][j-1]-(i-1)*S[i-1][j])%mod;
    }
    for (re int i=1;i<K;++i) fac[i]=fac[i-1]*i%mod;

    int T=read(),m=read();
    while (T--) {
        int l=read(),r=read(),k=read();
        if (m==2) {
            num<5> A=num<5>(0,1)/5,p=num<5>(1,1)/2;
            num<5> ans=solve(A,p,A.conj(),p.conj(),l+1,r+1,k);
            printf("%lld\n",(ans.x*qpow(r-l+1,mod-2)%mod+mod)%mod);
        } else {
            num<3> A=num<3>(3,1)/6,p=num<3>(2,1);
            num<3> ans=solve(A,p,A.conj(),p.conj(),(l+1)/2,r/2,k);
            printf("%lld\n",(ans.x*qpow(r-l+1,mod-2)%mod+mod)%mod);
        }
    }
    return 0;
}
最后修改:2019 年 10 月 04 日 05 : 10 PM

3 条评论

  1. xgzc

    Orz

  2. smy

    您常数怎么这么小啊qwq

    1. M_sea
      @smy

      我也不知道为什么跑的这么快qwq

发表评论