您的位置: 首页  >  IT文章  >  2018 11.1 PION 模拟赛

2018 11.1 PION 模拟赛

分类: IT文章 • 2025-01-27 08:02:08

期望：250  100+100+50

实际：210   80+100+30

2018 11.1 PION 模拟赛

2018 11.1 PION 模拟赛

 期望：100   实际：80

最后；两个点T了。可能是求逆元的方法太慢了，也可能是闲的又加了一个快速乘的原因。

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 1000000007
using namespace std;
int n,m;
long long ans;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
long long qmul(long long x,long long m){
    long long ret=0;
    while(m){
        if(m&1)
            ret=(ret+x)%mod;
        x=(x+x)%mod;
        m>>=1;
    }
    return ret;
}
long long ksm(long long a,long long n){
    long long ret=1;
    while(n){
        if(n&1)
            ret=qmul(ret,a)%mod;
        a=qmul(a,a)%mod;
        n>>=1;
    }
    return ret;
}
long long ex_gcd(long long a,long long b,long long &x,long long &y,long long &d){
    if(!b){ x=1;y=0;d=a; }
    else{
        ex_gcd(b,a%b,y,x,d);
        y-=(a/b)*x;
    }
}
long long inv(long long t,long long p){
    long long d,x,y;
    ex_gcd(t,p,x,y,d);
    return d==1?(x%p+p)%p:-1;
}
int main(){
    //freopen("lpp.in","r",stdin);
    freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++){
        if(i==1){ ans+=m;ans%=mod; }
        else{
            long long tmp=(ksm(i,m)-1)*inv((i-1),mod);
            ans=ans+qmul(tmp,i);
            ans%=mod;
        }
    }
    cout<<ans;
}
80TLE

后来明确了，就是因为在快速幂里套了一个快速乘，所以T了两个点。

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 1000000007
using namespace std;
int n,m;
long long ans;
int inv[50010];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
long long qmul(long long x,long long m){
    long long ret=0;
    while(m){
        if(m&1)
            ret=(ret+x)%mod;
        x=(x+x)%mod;
        m>>=1;
    }
    return ret;
}
long long fastpow(long long a,long long b){
    long long s=1;
    for(;b;b>>=1){
        if(b&1)    s=s*a%mod;
        a=a*a%mod; 
    }
    return s;
}
int main(){
    //freopen("lpp.in","r",stdin);
    freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    n=read();m=read();
    inv[1]=1;
    for(int i=2;i<=50000;i++)
        inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
    for(int i=1;i<=n;i++){
        if(i==1){ ans+=m;ans%=mod; }
        else{
            ans=ans+((fastpow(i,m)-1)*i)%mod*inv[i-1];
            ans%=mod;
        }
    }
    cout<<ans;
}
AC

 大佬们推公式的思路都好清奇 瑟瑟发抖ing

2018 11.1 PION 模拟赛

2018 11.1 PION 模拟赛

期望的分：100     实际得分：100

发现大家都用的求最长路，就我思路清奇写了个DP吗？(*^__^*) 

/*
期望的分：100
思路：树形dp 
*/
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 50010
using namespace std;
int n,tot;
int dad[MAXN],sum[MAXN],bns[MAXN],size[MAXN],dp[MAXN];
int to[MAXN*2],cap[MAXN*2],net[MAXN*2],head[MAXN];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void add(int u,int v,int w){
    to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot;
}
void dfs(int now){
    size[now]=1;
    for(int i=head[now];i;i=net[i])
        if(dad[now]!=to[i]){
            dad[to[i]]=now;
            dfs(to[i]);
            sum[now]+=sum[to[i]]+cap[i];
            size[now]+=size[to[i]];
        }
}
void pre(int now){
    if(size[now]==1)    dp[now]=0; 
    for(int i=head[now];i;i=net[i])
        if(dad[now]!=to[i])
            pre(to[i]);
}
void work(int now){
    int x;
    for(int i=head[now];i;i=net[i])
        if(dad[now]!=to[i]){
            work(to[i]);
            dp[now]=min(dp[to[i]]+cap[i]+(sum[now]-sum[to[i]]-cap[i])*2,dp[now]);
        }
}
int main(){
    //freopen("lpp.in","r",stdin);
    freopen("tour.in","r",stdin);
    freopen("tour.out","w",stdout);
    n=read();
    for(int i=1;i<n;i++){
        int u=read();
        int v=read();
        int w=read();
        add(u,v,w);add(v,u,w);
    }
    memset(dp,0x7f,sizeof(dp));
    dfs(1);
    pre(1);
    work(1);
    cout<<dp[1]; 
}
/*
9
1 2 2
2 4 2
2 3 3
1 5 1
5 6 2
5 7 6
6 8 4
6 9 5
*/
AC

2018 11.1 PION 模拟赛

2018 11.1 PION 模拟赛

期望：50    实际 ：30

读错题目了QwQ2018 11.1 PION 模拟赛想成了只有4和7是幸运数字。

这样竟然还有30分。。良心的出题人给你 笔芯❤❤❤

/*
期望的分：50
思路：暴力dfs 
*/
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 1000000007
using namespace std;
int n,k;
long long ans;
int a[100010],num[100010],vis[100010];
bool vis1[100010];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool judge(){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=k;i++)    vis[num[i]]++;
    for(int i=1;i<=k;i++)
        if(vis[num[i]]>=2&&vis1[num[i]])    return false;
    return true;
}
void dfs(int now,int tot){
    if(tot==k){
        if(judge()){
            ans++;
            ans%=mod;
        }
        return ;
    }
    if(now>n)    return ;
    num[tot+1]=a[now];dfs(now+1,tot+1);
    dfs(now+1,tot);
}
int main(){
    //freopen("lpp.in","r",stdin);
    freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
    n=read();k=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        int x=a[i],fl=0;
        while(x){
            if(x%10!=4&&x%10!=7)    fl=1;
            x/=10;
        }
        if(fl==0)    vis1[a[i]]=1;
        else vis1[a[i]]=0;
    }    
    dfs(1,0);
    printf("%I64d",ans);
}
50分暴力 
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <map>

using std::min;
using std::max;

typedef long long i64;
const i64 modulo = i64(1e9) + 7;
const int MaxN = 100005;
const int MaxM = 1024;

i64 power(i64 base, i64 k) {
    i64 res = 1;
    for ( ; k; k >>= 1) {
        if (k & 1) res = (res * base) % modulo;
        base = (base * base) % modulo;
    }
    return res;
}

i64 inv(i64 k) {
    return power(k, modulo - 2);
}

std::vector<i64> gen_lucky(i64 upper) {
    std::vector<i64> res; res.clear();
    std::vector<i64> a; a.clear(); a.push_back(0);
    for (int i = 0; i < 10; ++i) {
        std::vector<i64> b; b.clear();
        for (size_t j = 0; j < a.size(); ++j) {
            b.push_back(a[j] * 10 + 4);
            b.push_back(a[j] * 10 + 7);
        }
        if (b[0] < upper) {
            res.insert(res.end(), b.begin(), b.end());
            a = b;
        } else {
            return res;
        }
    }
    return res;
}

std::vector<i64> lucky;
std::map<i64, int> lucky2idx;
int n, m, unlucky, k, a[MaxN], cnt[MaxM];
i64 dp[MaxM][MaxM];
i64 f[MaxN];

i64 bincoef(int a, int b) {
    i64 tmp = f[a];
    tmp = tmp * inv(f[b]) % modulo;
    tmp = tmp * inv(f[a-b]) % modulo;
    return tmp;
}

int main(void) 
{   freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
    lucky = gen_lucky(1e9);
    m = lucky.size();
    for (int i = 0; i < m; ++i) {
        lucky2idx[lucky[i]] = i;
    }

    scanf("%d%d", &n, &k);
    unlucky = n;
    for (int i = 0; i < n; ++i) {
        scanf("%d", a+i);
        std::map<i64, int>::iterator it = lucky2idx.find(a[i]);
        if (it != lucky2idx.end()) ++cnt[it->second], --unlucky;
    }

    dp[0][0] = 1;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j <= i; ++j) {
            dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % modulo;
            dp[i+1][j+1] += (dp[i+1][j+1] + (dp[i][j] * cnt[i] % modulo)) % modulo;
        }
    }

    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i-1] * i % modulo;
    }

    i64 ans = 0;
    int st = max(0, k-m);
    int ed = min(k, unlucky);
    for (int i = st; i <= ed; ++i) {
        ans += dp[m][k-i] * bincoef(unlucky, i) % modulo;
        ans %= modulo;
    }

    printf("%d
", (int) ans);
    fclose(stdin);
    fclose(stdout);

    return 0;
}
std

相关推荐