1.11-526互联

昨天体侧测了 1000 米，因为之前下大雪一个月没怎么上体育，然后导致我体质变得很差，然后就只跑了 3 分 40，恼了。

风太大，起跑的时候没跟上人后面都是自己一个人跑，~~没人给我挡风~~,再加上周一练立定跳远把腿拉伤了，现在还疼，这种种因素下我认为我估计连进 4 分都难，结果 3 分 40 还是挺高兴的。

明天就是周五了又能看见她了 ???

emoji 恶心

超能粒子炮·改

题意是求 \(\sum_{i=0}^{k}\dbinom{i}{n}\%p\)

开始推，首先根据 Lucas 定理

\[\sum_{i=0}^{k}\dbinom{i}{n}=\sum_{i=0}^{k}\dbinom{i\%p}{n\%p}\times \dbinom{i/p}{n/p}\%p \]

由于 \(i/p\) 与 \(n/p\) 许多时候值相等，所以记

\[f[i]=\sum_{i=0}^{j}\dbinom{i\%p}{n\%p}\%p \]

预处理出 \(f\) 数组，但是仍然会 TLE

原因是我们在求 \(ans\) 时，需要这么写

for(;k<=m-p;k+=p) ans=(ans+f[n%p][n%p]*Lucas(n/p,k/p))%p;

这样写复杂度逆天，肯定是过不了啊。

所以我们提出 \(f[n\%p][n\%p]\)，就有

\[\sum_{i=0}^{m/p}\dbinom{i}{n/p} \]

然后发现可以递归求这个玩意

定义

\[F(i,j)=f[n\%p][n\%p]\times F(\frac np,\frac mp-1)+Lucas(\frac np,\frac mp)\times f[n\%p][min(n\%p,m\%p)] \]

然后就能求了

洛谷上交总是 40 分，发现原因竟然是递归函数写错了，这怎么拿的 40 ？？？

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 4001
#define p 2333
inline int read()
{
    int s = 0,w = 1;char ch = getchar();
    while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}
    while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}
    return s*w;
}
int n,m,c[N][N],f[N][N];
inline void inv(int &x)
{
    while(x<0) x+=p;
    while(x>=p) x-=p;
}
inline int Lucas(int n,int m)
{
    if(m==0) return 1;
    return c[n%p][m%p]*Lucas(n/p,m/p)%p;
}
inline int F(int n,int m)
{
    if(m<0) return 0;
    if(n<p && m<p) return f[n][m];
    return (F(n/p,m/p-1)*f[n%p][p-1]%p+Lucas(n/p,m/p)*f[n%p][m%p]%p)%p;
}
inline void init()
{
    c[0][0]=1;
    for(int i=1;i<p;++i)
    {
        c[i][i]=1,c[i][0]=1;
        for(int j=1;j<i;++j)
            {
                c[i][j]=c[i-1][j-1]+c[i-1][j];
                inv(c[i][j]);
            }
    }
    for(int i=0;i<p;++i)
    {
        f[i][0]=c[i][0];
        for(int j=1;j<p;++j)
            {
                f[i][j]=f[i][j-1]+c[i][j];
                inv(f[i][j]);
            }
    }
}
signed main()
{
    int t=read();
    init();
    while(t--)
    {
        n=read(),m=read();
        cout<<F(n,m)<<endl;
    }
}

前几天数学老师讲了讲多项式除法

一个典型的例子