• 周日. 7月 3rd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

NOIP需要掌握的一些stl库

admin

11月 28, 2021
/*
map
set
//bitset
vector
priority_queue

*/
#include <bits/stdc++.h>
using namespace std;



priority_queue <int,vector<int>,less<int> > a1;    //大根堆         priority_queue <int> a1
priority_queue <int,vector<int>,greater<int> > a2;    //小根堆 

struct node{
    int x,y;
};
bool operator<(node a,node b){
    return a.x<b.x;
}
priority_queue <node> a3;    

map <string,node> f;    //log(n)

vector<int> w;
vector<int> e[100005];



int main(){
    
    string s="ssd";
    f[s]=(node){3,4};
    
    w.push_back(3);    //w[0]=3;
//    w.resize(5);
//    w.size();
    
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
    }
    {
        int x=5,y;
        for (int i=0;i<e[x].size();++i){        //e[x].size:unsigned
            y=e[x][i];        //  x -> y
        }
    }
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mo=1000000007;
int minx,n,K,s[13],a[13],w[13],c[500005],d[500005],p[13],q[13],o[13],fl,ans,f[13],C[13][13];
int po(int x,int y){
    int z=1;
    for (;y;y>>=1,x=1ll*x*x%mo)
    if (y&1) z=1ll*z*x%mo;
    return z;
}
void solve(int n,int m){        //0^m +...+ n^m        f[0]~f[m]
    f[0]=n+1;
    for (int i=1;i<=m;++i){
        LL x=po(1+n,i+1);
        for (int j=0;j<i;++j) x=(x-1ll*C[i+1][j]*f[j])%mo;
        x=x*po(i+1,mo-2)%mo;
        f[i]=x;
    }
}
int main(){
    scanf("%d%d",&n,&K);
    C[0][0]=1;
    for (int i=1;i<=K+1;++i){
        C[i][0]=1;
        for (int j=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
    }
    while (1){
        int x,y;
        scanf("%d%d",&x,&y);
        solve(x,y);
    }
    
    for (int i=1;i<=K;++i) scanf("%d",&w[i]);
    for (int i=1;i<=n;++i) scanf("%d%d",&c[i],&d[i]);
    ans=1;
    for (int i=1;i<=K;++i) ans=1ll*ans*w[i]%mo;
    for (int i=1;i<=n;++i){
        o[c[i]]+=d[i];
        if (o[c[i]]>q[c[i]]) q[c[i]]++,w[c[i]]--;
        if (o[c[i]]<p[c[i]]) p[c[i]]--,w[c[i]]--;
        if (w[c[i]]==0) {fl=1; break;}
        LL x=1;
        for (int j=1;j<=K;++j) x=x*w[j]%mo;
        ans+=x; if (ans>=mo) ans-=mo;
    }
    if (fl){
        printf("%d
",ans);
        return 0;
    }
    {
        int fl=0;
        for (int i=1;i<=K;++i) if (o[i]) fl=1;
        if (!fl){
            puts("-1");
            return 0;
        }
    }
    for (int j=1;j<=K;++j) s[j]=o[j];
    for (int i=1;i<=n;++i){
        o[c[i]]+=d[i];
        if (o[c[i]]>q[c[i]]) q[c[i]]++,w[c[i]]--;
        if (o[c[i]]<p[c[i]]) p[c[i]]--,w[c[i]]--;
        if (w[c[i]]==0) break;
        
        for (int j=1;j<=K;++j) a[j]=0; a[0]=1;
        minx=1000000005;
        for (int j=1;j<=K;++j){
            //(w[j]-x*s[j]) * A
            if (s[j]!=0) minx=min((w[j]-1)/abs(s[j]),minx);
            for (int k=j;k>0;--k) a[k]=(-1ll*a[k-1]*s[j]+1ll*a[k]*w[j])%mo;
            a[0]=1ll*a[0]*w[j]%mo;
        }
        
        //0~minx
        solve(minx,K);
        for (int j=0;j<=K;++j) ans=(ans+1ll*a[j]*f[j])%mo;
    }
    printf("%d
",ans<0?ans+mo:ans);
    return 0;
}

View Code

转载请标明出处 http://www.cnblogs.com/cyz666/

发表评论

您的电子邮箱地址不会被公开。