NOIP提高组模拟赛夜间版1

由于上午考试出了其他大佬打过的原题,所以晚上加试

A. 中国象棋

一看题面,状压DP!一看数据范围\(N,M<=100\)。。。

实际可以发现,每行每列最多放两个炮,统计方案数的话具体在哪里是无所谓的

定义f[i][j][k]表示前i行有j个位置放了1个棋子,k个位置一个棋子都没放的方案数

初始状态f[0][0][m]=1;

分类讨论

不放\(f[i][j][k]=f[i-1][j][k]\)

放1个棋子在之前没放过的列,有\((k+1)\)种放法\(f[i][j][k]+=f[i-1][j-1][k+1]*(k+1)\)

放1个棋子在之前放过一个的列,有\((j+1)\)种放法\(f[i][j][k]+=f[i-1][j+1][k]*(j+1)\)

放2个棋子在之前没放过的列,有\((k+1)*(k+2)/2\)种放法\(f[i][j][k]+=f[i-1][j-2][k+2]*(k+1)*(k+2)/2\)

放2个棋子在之前放过1个的列,有\((j+1)*(j+2)\)种放法\(f[i][j][k]+=f[i-1][j+2][k]*(j+1)*(j+2)/2\)

放1个棋子在之前放过1个的列,1个棋子在之前没放过的列,有\(j*(k+1)\)种放法\(f[i][j][k]+=f[i-1][j][k+1]*j*(k+1)\)

记得取模,去掉减法减出负数的越界

最后答案对\(f[n][j][k](j\in[0,m],k\in[0,m])\)求和

#include<cstdio>
#include<algorithm>
using namespace std;
const int mod=9999973;
int n,m;
long long f[105][105][105];
int main(){
    scanf("%d%d",&n,&m);
    f[0][0][m]=1;//f[i][j][k] i行j个1k个0
    for(int i=1;i<=n;++i){
        for(int j=0;j<=m;++j){
            for(int k=0;k<=m;++k){
                f[i][j][k]+=f[i-1][j][k];//不放
                if(j)f[i][j][k]+=f[i-1][j-1][k+1]*(k+1);//放一个在没放过的列
                f[i][j][k]+=f[i-1][j+1][k]*(j+1);  //放一个在放过1个的列
                if(j>=2)f[i][j][k]+=f[i-1][j-2][k+2]*(k+2)*(k+1)/2;//放两个在没放过的列
                f[i][j][k]+=f[i-1][j+2][k]*(j+2)*(j+1)/2;//放两个在放过一个的列
                f[i][j][k]+=f[i-1][j][k+1]*j*(k+1);//放一个在没放过的列,1个在放过1个的列
                f[i][j][k]=f[i][j][k]%mod;
            }
        }
    }
    long long ans=0;
    for(int i=0;i<=m;++i)
      for(int j=0;j<=m;++j)
        ans=(ans+f[n][i][j])%mod;
    printf("%lld\n",ans);
    return 0;
}

B. 奇妙的 Fibonacci

奇妙奇妙,太奇妙了,大爱数论

感觉会敲latex到吐,提前祭奠一下

先说简单不用latex

考场直接打表,先敲个暴力,然后换用不同放法妄图探究性质,然后在输出第i项Fibonacci能整除第几项时发现了规律打表万岁,除了第二项特殊,其他第i项能整除第\(i,2*i,3*i,4*i.....k*i\)项,看到这个自然想到了埃氏筛,
yy了一下复杂度感觉能过,打完跑路,喜提TLE。线性筛也不会求这玩意啊

再来严谨的证明

\(fib[i]=fib[i-1]+fib[i-2]\)

\(=fib[i-1]*fib[2]+fib[i-2]*fib[1]\)

\(=(fib[i-2]+fib[i-3])*fib[2]+fib[i-2]*fib[1]\)

\(=fib[i-2]*fib[3]+f[i-3]f[2].........\)

同理可继续推下去有

\(fib[i]=fib[i-k+1]*fib[k]+fib[i-k]*fib[k-1]\)

即 \(fib[n+m]=fib[n]*fib[m+1]+fib[n-1]*fib[m]\) ......................\((1)\)

\(gcd(f_{i},f_{i-1})=gcd(f_{i}-f_{i-1},f_{i-1})=gcd(f_{i-2},f_{i-1})=....=gcd(f_{1},f_{2})=1\)......................\((2)\)

(因为(1))

\(gcd(fib_{n+m},fib_{m})=gcd(fib_{n-1}*fib_{m}+fib_{n}*fib_{m+1},fib_{m})\)

\(=gcd(fib_{n-1}*fib_{m}+fib_{n}*fib_{m+1}-fib_{m}-fib_{m}-fib_{m}...,fib_{m})\)

\(=gcd(fib_{n}*fib_{m+1},fib_{m})\)

(因为(2))

\(=gcd(fib_{n},fib_{m})\)

上式\(gcd(fib_{n+m},fib_{m})=gcd(fib_{n},fib_{m})\)与\(gcd(n+m,m)=gcd(n,m)\)类比

可以得出,对于相同n,m上述两个整除关系同时成立,也就是说\(i|j时fib_{i}|fib_{j}\)

这就是我打表打出的那个性质,也是解决问题的第一个关键点

经过这样的证明,我们可以将原问题转化为

对于i求i的约数个数和i约数的平方和

如何解决这个问题

考虑使用埃氏筛线性筛

定义

\(a[i]\)为i约数个数

\(b[i]\)为i约数平方和

\(c[i]\)为i最小质因子的幂

\(d[i]\)为i除去最小质因子后剩下的数

显然\(a[i],b[i]\)是积性函数

证明

\(m\perp n\)

\(m=p_{1}^{c1}p_{2}^{c2}p_{3}^{c3}...p_{n}^{cn}\)

\(a[m]=(c1+1)*(c2+1)*(c3+1)...(cn+1)\)

\(n=q_{1}^{x1}q_{2}^{x2}q_{3}^{x3}...q_{n}^{xn}\)

\(a[n]=(x1+1)*(x2+1)*(x3+1)...(xn+1)\)

\(mn=p_{1}^{c1}p_{2}^{c2}p_{3}^{c3}...p_{n}^{cn}q_{1}^{x1}q_{2}^{x2}q_{3}^{x3}...q_{n}^{xn}\)

\(a[mn]=(c1+1)*(c2+1)*(c3+1)...(cn+1)*(x1+1)*(x2+1)*(x3+1)...(xn+1)=a[m]*a[n]\)

关于\(b[i]\),用乘法分配律证明,过程。。。YY一下吧

大概就是对于n中每个因子,与m的每个因数相乘可以得到mn的一个因数,对平方和的贡献就是新因数的平方,也就是m因数的平方乘以n该因子的平方,将这串式子中的该因子平方提出来就能用b[m]和该因子表示新的平方和的一部分,而将所有n的因子都这样处理,可以YY得到\(b[mn]=b[m]b[n]\) \((m\perp n)\)

然后貌似就可以筛了

质数q \(A[q]=2\;\;B[q]=1+q^2\;\;C[q]=1\;\;D[q]=1\)

当$gcd(p,q)=1 $ 即\(i\;mod\;prime[j]!=0\)

$ A[pq]=A[p]A[q] ;;; B[pq]=B[p]B[q] ;;; C[pq]=1 ;;; D[pq]=p。$

当q|p时,即\(i\;mod\;prime[j]==0\)

\( A[pq]=A[p]/(C[p]+1)*(C[p]+2) \;\;\; B[pq]=B[p]+B[D[p]]*(p/D[p])^2 \)

\( C[pq]=C[p]+1 \;\;\; D[pq]=D[p]\)

解释一下\( A[pq]=A[p]/(C[p]+1)*(C[p]+2) \;\;\; B[pq]=B[p]+B[D[p]]*(p/D[p]*q)^2 \)

类似上面对积性的证明,考虑q这个质数(prime[j])对p因数的贡献,是\(q^{k}(k\in[0,c[p]])\)乘上不含q的因数,不含q的因数就有\(a[p]/(c[p]+1)\)个,现在有\(c[p]+1\)个q因子,那么对pq因子个数贡献就乘上\(c[p]+2\)

\(b[pq]\)与此类似,q对pq平方和的贡献是p中不含q的因数平方和乘上\(q^{c[p]+1}\)得出\(b[pq]=b[p]+b[d[p]]*q^{2c[p]+2}\),打快速幂也可,但是这个式子显然可以转化,因为\(p/d[p]=q^{c[p]}\),所以可以得到上式

最后因为\(fib_{2}=1\)是所有数的因数,所有奇数的a[i]需要++,不特判1,因为没说j小于i

#include<cstdio>
#include<cstring>

using namespace std;

const long long mod=1000000007;
const int maxx=10000007;
int ask[3000005];
long long a[maxx],b[maxx],c[maxx],d[maxx],prime[maxx];
bool flag[maxx];

int main(){
    int Q;scanf("%d",&Q);
    long long q,A,B,C;
    scanf("%lld%lld%lld%lld",&q,&A,&B,&C);
    for(int ass=1;ass<=Q;++ass){
        ask[ass]=q;
        q=(q*A+B)%C+1;
    }
    int cnt=0;
    a[1]=1,b[1]=1;
    for(int i=2;i<=C;++i){
        if(!flag[i]){
            prime[++cnt]=i;
            a[i]=2;b[i]=(1ll*i*i+1)%mod;c[i]=1;d[i]=1;
        }
        for(int j=1;j<=cnt&&prime[j]*i<=C;++j){
            int pq=i*prime[j];
            flag[pq]=1;
            if(i%prime[j]==0){
                a[pq]=(a[i]/(c[i]+1)*(c[i]+2))%mod;
                b[pq]=(b[i]+b[d[i]]*(i/d[i]*prime[j])*(i/d[i]*prime[j]))%mod;
                c[pq]=c[i]+1;
                d[pq]=d[i];
                break;
            }
            a[pq]=(1ll*a[i]*a[prime[j]])%mod;
            b[pq]=(1ll*b[i]*b[prime[j]])%mod;
            c[pq]=1;d[pq]=i;
        }

    }
    long long ans1=0,ans2=0;
    for(int i=1;i<=Q;++i){
        ans1=(ans1+a[ask[i]])%mod;
        ans2=(ans2+b[ask[i]])%mod;
        if(ask[i]&1){
            ans1++;
            ans2+=4;
        }
    }
    printf("%lld\n%lld\n",ans1%mod,ans2%mod);
    return 0;
}

貌似Day1神奇的函数不用暴力%prime[j],借鉴本题一小部分处理就行。

上一篇:Flowable入门系列文章84 - 流动的UI应用程序


下一篇:javascript当中Map Area Shape 和onmousemove的用法