NOIP 集训 DAY3

Posted on By 陈, 禹恩 NOIP 集训 DAY3无评论

今天有10题？？？

写了九题，懒得全写了，放代码

T1 https://www.luogu.com.cn/problem/CF294C

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long n,a[1005],q[1005],ll[1005],z[5005],ny[5005],m,b[1005],ls,pos,cnt,len,jc[1005];
long long ans=1;
long long ksm(long long aa,long long bb)
{
    ls=1;
    while(bb>0)
    {
        if(bb%2==1)
        {
            ls=(ls*aa)%mod;
        }
        bb/=2;
        aa=(aa*aa)%mod;
    }
    return ls;
}
void inti()
{
    z[0]=1;
    for(int i=1;i<=2000;i++)
    {
        z[i]=z[i-1]*i;
        z[i]%=mod;
    }
    ny[2000]=ksm(z[2000],mod-2);
    for(int i=1999;i>=1;i--)
    {
        ny[i]=ny[i+1]*(i+1);
        ny[i]%=mod;
    }
    jc[0]=1;
    for(int i=1;i<=1000;i++)
    {
        jc[i]=(jc[i-1]*2)%mod;
    }
}
long long C(long long aa,long long bb)
{
    ls=z[aa];
    ls=(ls*ny[bb])%mod;
    ls=(ls*ny[aa-bb])%mod;
    return ls;
}
int main()
{
    cin>>n>>m;
    inti();
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&b[i]);
    }
    sort(b+1,b+m+1);
    b[0]=0;
    if(b[1]!=1)
    {
        cnt++;
        ll[cnt]=b[1]-1;
        q[cnt]=1;
    }

    for(int i=2;i<=m;i++)
    {
        if(b[i]-b[i-1]>1)
        {
            cnt++;
            ll[cnt]=b[i]-b[i-1]-1;
            q[cnt]=jc[ll[cnt]-1];
        }
    }
    if(b[m]!=n)
    {
        cnt++;
        ll[cnt]=n-b[m];
        q[cnt]=1;
    }
    for(int i=1;i<=cnt-1;i++)
    {
        ans=(q[i]*q[i+1])%mod;
        ans=(ans*C(ll[i]+ll[i+1],ll[i]))%mod;
        q[i+1]=ans;
        ll[i+1]+=ll[i];
    }
    cout<<max(q[cnt],1ll);
    return 0;
}

T2 https://www.luogu.com.cn/problem/CF1753Chttps://www.luogu.com.cn/problem/CF1753C

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long T,n,a[200005],cnt,st,dp[200005],jc,ls;
long long ksm(long long aa,long long bb)
{
    ls=1;
    while(bb>0)
    {
        if(bb%2==1)
        {
            ls=(ls*aa)%mod;
        }
        bb/=2;
        aa=(aa*aa)%mod;
    }
    return ls;
}
int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%lld",&n);
        jc=1;
        st=0;
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            jc=jc*2;
            jc%=mod;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            if(a[i]==0) cnt++;
        }
        for(int i=1;i<=cnt;i++)
        {
            if(a[i]==0)
            {
                st++;
            }
        }
        if(st==cnt)
        {
            printf("0\n");
            continue;
        }
        dp[st]=0;
        for(int i=st+1;i<=cnt;i++)
        {
            dp[i]=(dp[i-1]+((n*(n-1)/2%mod)*ksm(((cnt-i+1)*(cnt-i+1))%mod,mod-2))%mod)%mod;
        }
        printf("%lld\n",dp[cnt]%mod);
        for(int i=1;i<=n;i++) dp[i]=0;
    }
    return 0;
}

T3 https://www.luogu.com.cn/problem/CF1657E
“`cpp

include

using namespace std;
const long long mod=998244353;
long long n,k,ls,dp[255][255],c[255][255],sum[255][255],ans;
long long ksm(long long aa,long long bb)
{
ls=1;
while(bb>0)
{
if(bb%21)
{
ls=(lsaa)%mod;
}
bb/=2;
aa=(aaaa)%mod;
}
return ls;
}
int main()
{
cin>>n>>k;
dp[1][0]=1;
for(int i=0;i<=k;i++) sum[1][i]=1;
c[0][0]=1;
for(int i=1;i<=n;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=2;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
for(int t=1;t<=i-1;t++)
{
dp[i][j]=dp[i][j]+(((sum[t][j-1]c[n-t][i-t])%mod)ksm(k-j+1,(i+t-3)*(i-t)/2))%mod;
dp[i][j]%=mod;
}
}
for(int j=1;j<=k;j++)
{
sum[i][j]=(sum[i][j-1]+dp[i][j])%mod;
}
}
cout<<sum[n][k]%mod;
return 0;
}

T4 https://www.luogu.com.cn/problem/CF660E

#include<bits/stdc++.h>
#define int long long
#define MX 1000005
using namespace std;
const int IX=MX; 
const int mod=1000000007ll;
int n,m,res,fac[MX],inv[MX];
int gmod(int ll){return ll%mod;}
void init(){
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=IX;i++) fac[i]=gmod(fac[i-1]*i);
    for(int i=2;i<=IX;i++) inv[i]=gmod(inv[i-(mod%i)]*(mod/i+1));
    for(int i=1;i<=IX;i++) inv[i]=gmod(inv[i]*inv[i-1]);
}
int C(int a,int b){
    if(a<b || a<0 || b<0)return 0;
    return gmod(fac[a]*gmod(inv[a-b]*inv[b]));
}
int qm(int a,int b){
    int x=1,c=a;
    while(b){
        if(b&1){x=gmod(x*c);}
        b>>=1;c=gmod(c*c);
    }
    return x;
}
signed main(){
    cin.tie(0);cout.tie(0);
    init();cin>>n>>m;res=qm(m,n);
    for(int i=1;i<=n;i++)
        res=gmod(res+gmod(qm(m,i)*qm(m-1,n-i))*C(n,i-1));
    cout<<res<<&#039;\n&#039;;
    return 0;
}

T5 https://www.luogu.com.cn/problem/CF785D

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long n,l[200005],r[200005],z[200005],ny[200005],ls,ans;
string a;
long long ksm(long long aa,long long bb)
{
    ls=1;
    while(bb>0)
    {
        if(bb%2==1)
        {
            ls=(ls*aa)%mod;
        }
        bb/=2;
        aa=(aa*aa)%mod;
    }
    return ls;
}
void inti()
{
    z[0]=1;
    for(int i=1;i<=200000;i++)
    {
        z[i]=z[i-1]*i;
        z[i]%=mod;
    }
    ny[200000]=ksm(z[200000],mod-2);
    for(int i=199999;i>=1;i--)
    {
        ny[i]=ny[i+1]*(i+1);
        ny[i]%=mod;
    }
    ny[0]=1;
}
long long C(long long aa,long long bb)
{
    if(aa<bb) return 0;
    ls=z[aa];
    ls=(ls*ny[bb])%mod;
    ls=(ls*ny[aa-bb])%mod;
    return ls;
}
int main()
{
    cin>>a;
    n=a.size();
    a=" "+a;
    inti();
    for(int i=1;i<=n;i++)
    {
        l[i]=l[i-1];
        if(a[i]==&#039;(&#039;) l[i]++;
    }
    for(int i=n;i>=1;i--)
    {
        r[i]=r[i+1];
        if(a[i]==&#039;)&#039;) r[i]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]==&#039;(&#039;)
        {
            ans+=C(l[i]+r[i+1]-1,l[i]);
            ans%=mod;
        }
    }
    cout<<ans;
    return 0;
}

T6 https://www.luogu.com.cn/problem/CF1540B

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long n,u,v,ls,z[205],ny[205],ans,fa[205][10],deep[205],dp[205][205],lca;
vector<int> G[205];
long long ksm(long long aa,long long bb)
{
    ls=1;
    while(bb>0)
    {
        if(bb%2==1)
        {
            ls=(ls*aa)%mod;
        }
        bb/=2;
        aa=(aa*aa)%mod;
    }
    return ls;
}
void inti()
{
    z[0]=1;
    for(int i=1;i<=200;i++)
    {
        z[i]=z[i-1]*i;
        z[i]%=mod;
    }
    ny[200]=ksm(z[200],mod-2);
    for(int i=199;i>=1;i--)
    {
        ny[i]=ny[i+1]*(i+1);
        ny[i]%=mod;
    }
    ny[0]=1;
}
void dfs(int x,int f)
{
    deep[x]=deep[f]+1;
    fa[x][0]=f;
    for(int i=1;i<=9;i++)
    {
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }
    for(int i=0;i<G[x].size();i++)
    {
        if(G[x][i]!=f)
        {
            dfs(G[x][i],x);
        }
    }
    return ;
}
int LCA(int x,int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=9;i>=0;i--)
    {
        if(deep[fa[x][i]]>=deep[y]) x=fa[x][i];
    }
    if(x==y)
    {
        return x;
    }
    for(int i=9;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i]) 
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
int main()
{
    inti();
    cin>>n;
    for(int i=1;i<=n-1;i++)
    {
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++) dp[0][i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])*ny[2];
            dp[i][j]%=mod;
        }
    }
    for(int i=1;i<=n;i++)
    {   
        //memset(fa[i],0,sizeof(fa[i]));
        dfs(i,0);
        for(int j=1;j<=n;j++)
        {
            for(int h=1;h<j;h++)
            {
                lca=LCA(j,h);
                //cout<<lca<<endl;
                ans+=dp[deep[j]-deep[lca]][deep[h]-deep[lca]];
                ans%=mod;
            }
        }
    }
    //cout<<ans<<&#039; &#039;;
    cout<<(ans*ksm(n,mod-2))%mod;
    return 0;
}

(md真不想写这*blog了)

T7 https://www.luogu.com.cn/problem/CF1716F

#include <bits/stdc++.h>
#define int long long
#define MX 2005
using namespace std;
const int mod=998244353;
int T,n,m,x,v,k,ans,s[MX][MX];
int gmod(int ll){return ll%mod;}
int qm(int a,int b){
    int x=1,c=a;
    while(b){
        if(b&1){x*=c;}
        b>>=1;c*=c;
        x%=mod;c%=mod;
    }
    return x;
}
signed main(){
    cin.tie(0);cout.tie(0);
    s[0][0]=1;
    for(int i=1;i<=2000;i++)
    for(int j=1;j<=i;j++)
        s[i][j]=gmod(s[i-1][j-1]+s[i-1][j]*j);
    cin>>T;
    while(T--){
        cin>>n>>m>>k;ans=0;x=(m+1)>>1;
        v=gmod(gmod(x*qm(m,n-1))*n);m=qm(m,mod-2);
        for(int i=1;i<=min(n,k);i++){
            ans=gmod(ans+s[k][i]*v);
            v=gmod(v*gmod(gmod(x*m)*(n-i)));
        }cout<<ans<<&#039;\n&#039;;
    } 
    return 0;
}

T8 https://www.luogu.com.cn/problem/CF1437F

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long ls,z[5005],ny[5005],n,a[5005],lim[5005],dp[5005];
long long ksm(long long aa,long long bb)
{
    ls=1;
    while(bb>0)
    {
        if(bb%2==1)
        {
            ls=(ls*aa)%mod;
        }
        bb/=2;
        aa=(aa*aa)%mod;
    }
    return ls;
}
void inti()
{
    z[0]=1;
    for(int i=1;i<=5000;i++)
    {
        z[i]=z[i-1]*i;
        z[i]%=mod;
    }
    ny[5000]=ksm(z[5000],mod-2);
    for(int i=4999;i>=1;i--)
    {
        ny[i]=ny[i+1]*(i+1);
        ny[i]%=mod;
    }
    ny[0]=1;
}
long long A(long long aa,long long bb)
{
    if(aa<0||bb<0||aa<bb) return 0;
    ls=z[aa];
    ls=(ls*ny[aa-bb])%mod;
    return ls;
}
int main()
{
    inti();
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    int l,r,mid;
    a[0]=0;
    for(int i=1;i<=n;i++)
    {
        l=0;
        r=i-1;
        while(l<r)
        {
            mid=(l+r)/2+1;
            if(a[mid]*2<=a[i]) l=mid;
            else r=mid-1;
        }
        lim[i]=l;
//      cout<<lim[i]<<endl;
    }
    dp[0]=1;
    lim[0]=-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=lim[i];j++)
        {
            dp[i]=dp[i]+dp[j]*A(n-2-lim[j],lim[i]-lim[j]-1);
            dp[i]%=mod;
        }
    //  cout<<dp[i]<<endl;
    }
    if(lim[n]==n-1) cout<<dp[n];
    else cout<<"0";
    return 0;
}

T10 https://www.luogu.com.cn/problem/CF1626F

#include <bits/stdc++.h>
#define int long long
#define MX 10000005
using namespace std;
const int mod=998244353;
int n,a[MX],x,y,k,M,dp[20][720721],g[20],ans,sum;
int gmod(int ll){return ll-ll/mod*mod;}
signed main(){
    cin.tie(0);cout.tie(0);
    cin>>n>>a[0]>>x>>y>>k>>M;g[0]=1;
    for(int i=1;i<k;i++) g[i]=gmod(g[i-1]*n);
    for(int i=1;i<n;i++) a[i]=(a[i-1]*x+y)%M; 
    M=720720;
    for(int i=0;i<n;i++){
        sum=gmod(sum+a[i]);
        dp[0][a[i]%M]++;
    }ans=gmod(g[k-1]*sum);
    for(int i=1;i<=k;i++){
        //cout<<ans<<&#039; &#039;<<sum<<&#039;\n&#039;;
        sum=gmod(sum*n);
        for(int j=0;j<M;j++){
            dp[i][j]=gmod(dp[i-1][j]*(n-1));
            dp[i][j-(j%i)]=gmod(dp[i][j-(j%i)]+dp[i-1][j]);
            sum=gmod(gmod(sum-dp[i-1][j]*(j%i))+mod);
        }
        if(i<k) ans=gmod(ans+g[k-i-1]*sum);
    }cout<<ans<<&#039;\n&#039;;
    return 0;
}
训练日志

发表回复