毒枭模拟 noip 11.08

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int inf=0x3f3f3f3f3f3f3f3f;
int q,a,b,c,d,x,ans;
bool comp(int a,int y,int z){
    if(z<0)return true;
    if(a<0||y<0)return true;
    if(y==0)return z<0;
    else return a>z/y;
}
int check(int s){
    int fi=a+b*(s-1);
    if(fi<c)return 0;
    return (fi-c)/d+1;
}
int get(int s){
    int fi=a*s+b*s*(s-1)/2;
    if(s==0)fi=0;
    int l=0,r=x-fi,mid;
    while(l<r){
        mid=l+r+1>>1;
        int sum=c*mid+d*(mid-1)*mid/2;
        if(comp(d,mid-1,x-c)||comp(c,mid,x)||comp(d,mid*(mid-1)/2,x)||sum>x-fi||sum<0)r=mid-1;
        else l=mid;
    }
    return l;
}
signed main(){
    freopen("money.in","r",stdin);
    freopen("money.out","w",stdout);
    scanf("%lld",&q);
    while(q--){
        scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&x);
        int l=1,r=x,mid,s2,s3;
        while(l<r){
            mid=l+r+1>>1;
            s2=a*mid+b*mid*(mid-1)/2;
            int ck=check(mid);
            s3=c*ck+d*ck*(ck-1)/2;if(ck==0)s3=0;
            if(comp(c,ck,x)||comp(d,ck*(ck-1)/2,x)||s3<0||s3>x)r=mid-1;
            else if(comp(a,mid,x)||comp(b,mid*(mid-1)/2,x)||s2<0||s2>x||s2+s3>x||s2+s3<0)r=mid-1;
            else l=mid;
        }ans=get(0);
        if(a*l+b*l*(l-1)/2>0&&a*l+b*l*(l-1)/2<=x){
            ans=max(ans,l+get(l));
            if(l>=1&&a*(l-1)+b*(l-2)*(l-1)/2>0&&a*(l-1)+b*(l-2)*(l-1)/2<=x)ans=max(ans,l-1+get(l-1));
        }
        printf("%lld\n",ans);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int inf=0x3f3f3f3f3f3f3f3f;
int n,mod,w,m,ans;
int ksm(int x,int y){
    int ret=1;
    while(y){
        if(y&1)ret=ret*x%mod;
        x=x*x%mod;y>>=1;
    }return ret;
}
int dp[405][9005];
int dfs(int x,int y){
    if(!y||!x)return 1;
    if(~dp[x][y])return dp[x][y];
    dp[x][y]=0;
    fo(i,max(0ll,y-9*(x-1)),min(9ll,y)){
        dp[x][y]=dp[x][y]+dfs(x-1,y-i);
    }
    return dp[x][y];
}
void get_ans(int x,int y,int lim){
    if(!x||!y)return ;
    int now=lim;
    fo(i,max(0ll,y-9*(x-1)),min(9ll,y)){
        int del=dfs(x-1,y-i);
        if(now<=dfs(x-1,y-i)){
            ans=(ans*10ll+i)%mod;
            get_ans(x-1,y-i,now);
            break;
        }
        now-=del;
    }
}
signed main(){
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    memset(dp,-1,sizeof(dp));
    scanf("%lld%lld",&n,&mod);
    fo(t,1,min(n,13ll)){
        w=t*t*t;m=t*t*t*t;
        bool fl=false;ans=0;
        fo(i,1,inf){
            fo(j,max(1ll,w-9*(i-1)),min(9ll,w)){
                int now=dfs(i-1,w-j);
                if(m<now){
                    fl=true;ans=j;
                    // cout<<j<<endl;
                    get_ans(i-1,w-j,m);
                    printf("%lld",ans);
                    printf(" ");
                    break;
                }
                m-=now;
            }
            if(fl)break;
        }
    }
    int bas=0,p=ksm(10,40000);
    fo(i,1,40000)bas=(bas*10+9)%mod;
    fo(t,14,n){
        w=t*t*t;m=t*t*t*t;
        int now=w%9+2,sb=w/9;
        //cout<<now<<endl;
        // cout<<sb*(sb+1)/2<<" "<<m<<endl;
        ans=now;m-=1+sb;
        if(ans>9)ans=(ans%9*10+9)%mod;
        fo(i,1,sb/40000)ans=(ans*p+bas)%mod;
        fo(i,1,sb%40000)ans=(ans*10ll+9)%mod;
        if(now>9)sb++;
        fo(i,1,sb){
            if(m<=sb-i+1){
                //cout<<i<<" "<<sb-i+1-m<<endl;
                ans=(ans-ksm(10,sb-i)+mod)%mod;
                ans=(ans-ksm(10,sb-i+1-m)+mod)%mod;
                printf("%lld ",ans);
                break;
            }
            m-=sb-i+1;
        }
    }
    return 0;
}