QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#328508#7881. Computational Complexitysumi007WA 25ms7020kbC++233.6kb2024-02-15 20:36:312024-02-15 20:36:31

Judging History

你现在查看的是最新测评结果

  • [2024-02-15 20:36:31]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:7020kb
  • [2024-02-15 20:36:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define i128 __int128
#define db double
#define ldb long double
#define ull unsigned long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(i) (i&-i) 
const ll M = 1e15,N = 2e6+77; 
ll f[N],g[N],c[N],idx,mod,m,val[N];
ll t[10],vis[2][N],a[N],sum[2][N]; 
unordered_map<ll,int> id;
ll check(int c2,int c3,int c5,int c7){
    i128 x = (1ll<<c2);if(x>M) return 0;
    x = x*pow(3,c3);if(x>M) return 0;
    x = x*pow(5,c5);if(x>M) return 0;
    x = x*pow(7,c7);if(x>M) return 0;
    return (ll)x;  
}
int get_id(int c2,int c3,int c5,int c7){
    ll x = check(c2,c3,c5,c7);
    if(!id[x]) id[x] = ++idx,val[idx] = x;
    return id[x]; 
}
void gmod(ll &x){
    if(x>=mod) x -= mod;
    if(x<0) x += mod;
}
ll bf(ll x,ll op){
    ll res = x; 
    if(!op){
        if(!x) return f[0];
        res = max(res,bf(x/2,1)+bf(x/3,1)+bf(x/5,1)+bf(x/7,1));
    }else{
        if(!x) return g[0];
        res = max(res,bf(x/2,0)+bf(x/3,0)+bf(x/4,0)+bf(x/5,0));
    }
    res %= mod;
    return res;
}
ll calc(int c2,int c3,int c5,int c7,int op){
    ll u = get_id(c2,c3,c5,c7);
    if(val[u]<=14 || vis[op][u]){
        if(op==1) return g[u];
        else return f[u];
    }
    vis[op][u] = 1;
    if(op){ 
        if(c2) g[u] += calc(c2-1,c3,c5,c7,0),gmod(g[u]);
        if(c3) g[u] += calc(c2,c3-1,c5,c7,0),gmod(g[u]);
        if(c2>1) g[u] += calc(c2-2,c3,c5,c7,0),gmod(g[u]);
        if(c5) g[u] += calc(c2,c3,c5-1,c7,0),gmod(g[u]);
        return g[u];
    }else{
        if(c2) f[u] += calc(c2-1,c3,c5,c7,1),gmod(f[u]);
        if(c3) f[u] += calc(c2,c3-1,c5,c7,1),gmod(f[u]);
        if(c5) f[u] += calc(c2,c3,c5-1,c7,1),gmod(f[u]);
        if(c7) f[u] += calc(c2,c3,c5,c7-1,1),gmod(f[u]);
        return f[u];
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    ll V,T;
    V = M;while(V) t[2]++,V /= 2;
    V = M;while(V) t[3]++,V /= 3;
    V = M;while(V) t[5]++,V /= 5;
    V = M;while(V) t[7]++,V /= 7;
    cin >> f[0] >> g[0] >> T >> mod;idx = 14;
    f[0] %= mod,g[0] %= mod;
    for(int i=1;i<=14;i++) f[i] = bf(i,0),g[i] = bf(i,1),id[i] = i,val[i] = i;
    for(int i=1;i<=14;i++) c[i] = f[i]-f[i-1],gmod(c[i]);
    for(int i=1;i<=14;i++) f[i] = c[i];
    for(int i=1;i<=14;i++) c[i] = g[i]-g[i-1],gmod(c[i]);
    for(int i=1;i<=14;i++) g[i] = c[i];    
    for(int i=t[2];i>=0;i--){
        for(int j=t[3];j>=0;j--){
            for(int k=t[5];k>=0;k--){
                for(int l=t[7];l>=0;l--){
                    ll ck = check(i,j,k,l);
                    if(!ck) continue;
                    calc(i,j,k,l,0);
                    calc(i,j,k,l,1);
                }
            }
        }
    }
    for(int i=1;i<=idx;i++) a[i] = i;
    sort(a+1,a+1+idx,[&](int x,int y){return val[x]<val[y];});
    for(int i=1;i<=idx;i++){
        sum[0][i] = sum[0][i-1]+f[a[i]],gmod(sum[0][i]);
        sum[1][i] = sum[1][i-1]+g[a[i]],gmod(sum[1][i]);
    }
    for(int i=1;i<=20;i++) cout << a[i] << ' ';
    cout << '\n';
    while(T--){
        ll x;cin >> x;
        int l = 1,r = idx,k = 0;
        while(l<=r){
            int mid = (l+r)>>1;
            if(val[a[mid]]<=x){
                k = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        cout << (f[0]+sum[0][k])%mod << ' ' << (g[0]+sum[1][k])%mod << '\n'; 
    }
    return 0;
}
// 1958 920 10 100000000000
// 0
// 1
// 2
// 3
// 10
// 100
// 200
// 1000
// 19580920
// 20232023

详细

Test #1:

score: 0
Wrong Answer
time: 25ms
memory: 7020kb

input:

1958 920 10 100000000000
0
1
2
3
10
100
200
1000
19580920
20232023

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 60 244 152 380 106 198 
1958 920
3680 7832
10592 9554
17504 11276
50294 64826
778850 897086
1935782 1986356
13378862 14504168
98149984406 90796344970
69705511990 65131718724

result:

wrong answer 1st numbers differ - expected: '1958', found: '1'