NOIP模拟34

川长思鸟来 2023-08-17 16:48 117阅读 0赞

考试的时候被T2卡了一年。。。。考虑了一下正解的式子，然后没去给左边分解因数，去给后面乘倍数。。。理论复杂度O（n^2），实际好像卡不掉的样子。但是由于我智障的打了一棵主席树，他M了。。。。

预计得分100+？？+20，实际得分100+70+20

T3，

这道题dp式子想一想就出来了，但是由于模数不保证质数，如果用组合数要exlucas，其实可以不用组合数，但是由于我过于智障，还是打了组合数打法，但是由于我不会懒得打ex，于是我们可以。。。。。分解质因数。。。。。

首先求出1到m每个数的质因子，然后对于组合数分解成质因数相乘的形式，如果每求一个组合数都暴力将所有质因子乘一遍的话，显然会死，考虑优化：

从当前组合数递推到下一个质组合数只需要乘一个数，再除掉一个数，我们观察到除掉的那个数必然<5000，于是我们可以每次将小于5000的质因子暴力乘一遍，再乘上大于5000的质因子的乘积，那么复杂度就对了。

注意在求每个数的质因子时，我们不需要每个数O(sqrt(n))求，可以在线筛的同时处理出来，具体来说，i×pri的质因子一定只比i多一个pri，我们可以记录每个数的前趋是谁，这样复杂度O（n），也可以直接让乘积继承i的vector，复杂度和埃氏筛一样，为O（nloglogn），都是可以接受的。

代码比exlucas短，效率也快很多（虽然不如不用组合数）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 #define ll long long
     3 using namespace std;
     4 int n,m,p,pri[1000005],tot,mx,a[1000005];
     5 vector<int>h[1000005];
     6 char v[1000005];
     7 ll num[5005][5005],f[2][5005],c[5005],aa=1,sum[1000005];
     8 inline int read(int x=0,char ch=getchar()){
     9     while(ch<'0'||ch>'9')ch=getchar();
    10     while(ch>='0'&&ch<='9')x=x*10-48+ch,ch=getchar();
    11     return x;
    12 }
    13 inline ll qpow(ll x,ll y,ll ans=1){
    14     for(;y;y>>=1,x=x*x%p)
    15         if(y&1)
    16             ans=ans*x%p;
    17     return ans;
    18 }
    19 signed main(){
    20     scanf("%d%d%d",&n,&m,&p);
    21     for(int i=1;i<=n;i++) a[i]=read(),mx=max(mx,a[i]);
    22     for(int i=2;i<=m;i++){
    23         if(!v[i]) pri[++tot]=i,h[i].push_back(i);
    24         for(int j=1;j<=tot&&i*pri[j]<=m;j++){
    25             v[i*pri[j]]=true;
    26             h[i*pri[j]]=h[i];
    27             h[i*pri[j]].push_back(pri[j]);
    28             if(i%pri[j]==0) break;
    29         }
    30     }
    31     for(int j=0;j<h[m].size();j++){
    32         if(h[m][j]>5000)aa=aa*h[m][j]%p;
    33         else sum[h[m][j]]++;
    34     }
    35     for(int i=1;i<=min(mx,m);i++){
    36         c[i]=aa;
    37         for(int j=1;j<=tot&&pri[j]<=5000;j++)
    38             c[i]=c[i]*qpow(pri[j],sum[pri[j]])%p;
    39         if(i!=min(mx,m)){
    40             for(int j=0;j<h[i+1].size();j++)
    41                 sum[h[i+1][j]]--;
    42             for(int j=0;j<h[m-i].size();j++)
    43                 if(h[m-i][j]>5000)aa=aa*h[m-i][j]%p;
    44                 else sum[h[m-i][j]]++;
    45         }
    46     }
    47     num[0][0]=1;
    48     for(int i=1;i<=mx;i++)
    49         for(int j=1;j<=min(mx,m);j++)
    50             num[i][j]=(num[i-1][j-1]*j+num[i-1][j]*(j-1))%p;
    51     for(int i=1;i<=min(a[1],m);i++)
    52         f[1][i]=num[a[1]][i]*c[i]%p,sum[1]=(sum[1]+f[1][i])%p;
    53     for(int i=2;i<=n;i++){
    54         sum[i]=0;
    55         for(int j=1;j<=min(a[i],m);j++){
    56             f[i&1][j]=((sum[i-1]*num[a[i]][j]%p*c[j]-(j<=a[i-1])*f[(i-1)&1][j]*num[a[i]][j])%p+p)%p;
    57             sum[i]=(sum[i]+f[i&1][j])%p;
    58         }
    59     }
    60     printf("%lld\n",sum[n]);
    61     return 0;
    62 }

转载于:https://www.cnblogs.com/hzoi-cbx/p/11447419.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/081463279fa94cf291ef227daea4f05c.png