QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#345707 | #4793. Qnp | Kevin5307 | WA | 1346ms | 23300kb | C++20 | 2.4kb | 2024-03-07 12:42:27 | 2024-03-07 12:42:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define sz(v) (int)((v).size())
using ll=long long;
using i128=__int128_t;
const ll thres=(ll)(1e18)+10;
vector<ll> vC[70007];
inline ll C(int n,int k)
{
k=min(k,n-k);
return k>=sz(vC[n])?thres:vC[n][k];
}
inline ll mul(ll a,ll b)
{
if(1.*a*b>thres) return thres;
return a*b;
}
ll val[70007];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for(int i=1;i<70007;i++)
val[i]=thres/i+(i!=1);
for(int i=0;i<70007;i++)
{
vC[i].resize(min(30,i+1));
vC[i][0]=1;
for(int j=1;j<sz(vC[i]);j++)
if(j==i)
vC[i][j]=1;
else
vC[i][j]=min(thres,vC[i-1][j]+vC[i-1][j-1]);
}
int q;
cin>>q;
while(q--)
{
static int c[12];
for(int i=0;i<10;i++)
cin>>c[i];
ll k;
cin>>k;
const ll mod=1e9+7;
ll ans=0;
int cur2=0;
int sum=accumulate(c,c+10,0);
ll ways=thres;
while(sum--)
{
int tmp=sum+1;
while(!c[cur2]) cur2++;
int mx=0;
for(int i=0;i<10;i++)
mx=max(mx,c[i]);
if(ways==thres&&sum-mx<=25)
{
if(mx>25)
{
int pos=0;
for(int i=0;i<10;i++)
if(c[i])
pos=i;
int l=0,r=c[pos];
while(l<r)
{
int mid=(l+r)/2;
ll tmp=1;
int total=sum+1-c[pos]+mid;
for(int i=0;i<10;i++)
{
int cur=(i==pos?mid:c[i]);
tmp=mul(tmp,C(total,cur));
total-=cur;
}
assert(!total);
if(tmp<k)
l=mid+1;
else
r=mid;
}
if(l!=c[pos])
{
ans=(ans*10+pos)%mod;
c[pos]--;
while(c[pos]!=l)
{
c[pos]--;
sum--;
ans=(ans*10+pos)%mod;
}
continue;
}
}
ways=1;
for(int i=cur2;i<9;i++)
{
ways=mul(ways,C(tmp,c[i]));
if(ways>=thres) break;
tmp-=c[i];
}
}
else if(ways==thres)
{
c[cur2]--;
ans=(ans*10+cur2)%mod;
while(c[cur2]>30)
{
c[cur2]--;
ans=(ans*10+cur2)%mod;
sum--;
}
continue;
}
int cur=cur2;
while(cur<10)
{
if(!c[cur])
{
cur++;
continue;
}
ll ways2=(ways>=val[c[cur]]?thres:ways*c[cur]/(sum+1));
if(ways2<k)
{
k-=ways2;
cur++;
}
else
{
ways=ways2;
break;
}
}
ans=(ans*10+cur)%mod;
c[cur]--;
}
cout<<ans<<'\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 6ms
memory: 23300kb
input:
6 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 2 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 2 1 1 1 0 0 0 0 0 0 0 5 1 2 0 0 0 0 0 0 0 0 2
output:
1 10 12 21 201 101
result:
ok 6 numbers
Test #2:
score: -100
Wrong Answer
time: 1346ms
memory: 23268kb
input:
5000 7142 6835 7022 6981 6929 7008 7038 7015 6885 7145 659213485437 7015 7033 6963 7136 7053 7072 6847 6923 6953 7005 82053183749 7013 7003 6969 7000 7011 7137 7030 6823 7021 6993 817812793310 6893 7008 6963 7086 7012 6922 7128 7094 7028 6866 143084249211 7020 7021 6997 6961 7017 7032 7013 7028 6987...
output:
324026044 934681423 580333699 357954149 997583122 487779276 509804693 195051680 874386711 663258863 945212961 461878500 713553299 401201422 942669409 812183215 999636681 908044156 274131029 159993616 988367425 39935074 376548240 640475777 422520550 193666086 769483179 610329846 354605523 325744457 6...
result:
wrong answer 1st numbers differ - expected: '190295171', found: '324026044'