QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #643748 | #7954. Special Numbers | ucup-team3474 | Compile Error | / | / | C++20 | 15.5kb | 2024-10-15 23:43:04 | 2024-10-15 23:43:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N=1919810,mod=1e9+7;
ll n;
string L,R;
int cnt[10];
vector<ll> v;
map<__int128,int> mp;
ll f2[30][2];
ll d2[30][2];
ll f[26][70][45][40][30][2];
ll dp[26][70][45][40][30][2];
int c[10];
ll cal(string s){
reverse(s.begin(),s.end());
if(s=="0") return 0;
s=" "+s;
memset(d2,0,sizeof d2);
int sz=s.size()-1;
ll sum=0;
for(int i=1;i<sz;i++){
for(int j=1;j<=9;j++){
sum+=f2[i-1][1];
sum%=mod;
}
}
//cout<<sum<<endl;
d2[sz][1]=sum;
int state=0;
for(int i=sz;i>0;i--){
int tt=s[i]-'0';
for(int j=0;j<tt;j++){
if(i==sz&&j==0) continue;
for(int u=0;u<=1;u++){
int ns=state|u;
if(j==0) ns=1;
d2[i][ns]+=f2[i-1][u];
d2[i][ns]%=mod;
}
}
if(s[i]=='0') state=1;
}
ll ans=0;
if(state) ans=1;
for(int i=1;i<=sz;i++){
//cout<<d2[i][1]<<endl;
ans=(ans+d2[i][1])%mod;
}
//cout<<ans<<endl;
return ans;
}
string trans(string s){
//if(!flag) return s;
__int128 xx=0;
for(int i=0;i<s.size();i++){
int t=s[i]-'0';
xx=xx*10+t;
}
xx--;
string ss;
while(xx){
int t=xx%10;
//cout<<t<<endl;
char ch=t+'0';
ss+=ch;
xx/=10;
}
if(ss.size()==0) ss="0";
reverse(ss.begin(),ss.end());
//cout<<ss<<endl;
return ss;
}
void work2(){
f2[0][0]=1;
for(int i=1;i<=25;i++){
for(int j=0;j<=9;j++){
if(j==0){
(f2[i][1]+=(f2[i-1][0]+f2[i-1][1]))%=mod;
}else{
(f2[i][0]+=f2[i-1][0])%=mod;
(f2[i][1]+=f2[i-1][1])%=mod;
}
}
}
//cout<<f2[1][1]<<endl;
cout<<(cal(R)-cal(trans(L))+mod)%mod<<endl;
}
ll Cal(string s){
reverse(s.begin(),s.end());
if(s=="0") return 0;
s=" "+s;
memset(dp,0,sizeof dp);
int sz=s.size()-1;
ll sum=0;
ll st2=0,st3=0,st5=0,st7=0,st0=0;
for(int i=1;i<sz;i++)
for(int t2=0;t2<=c[1];t2++){
for(int t3=0;t3<=c[2];t3++){
for(int t5=0;t5<=c[3];t5++){
for(int t7=0;t7<=c[4];t7++){
for(int t0=0;t0<=c[0];t0++){
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt0=1;
if(nt2==c[1]&&nt3==c[2]&&nt5==c[3]&&nt7==c[4]&&nt0==c[0])
(sum+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt2++;
nt2=min(nt2,c[1]);
if(nt2==c[1]&&nt3==c[2]&&nt5==c[3]&&nt7==c[4]&&nt0==c[0])
(sum+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt3++;
nt3=min(nt3,c[2]);
if(nt2==c[1]&&nt3==c[2]&&nt5==c[3]&&nt7==c[4]&&nt0==c[0])
(sum+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt2+=2;
nt2=min(nt2,c[1]);
if(nt2==c[1]&&nt3==c[2]&&nt5==c[3]&&nt7==c[4]&&nt0==c[0])
(sum+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt5++;
nt5=min(nt5,c[3]);
if(nt2==c[1]&&nt3==c[2]&&nt5==c[3]&&nt7==c[4]&&nt0==c[0])
(sum+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt2++;
nt3++;
nt2=min(nt2,c[1]);
nt3=min(nt3,c[2]);
if(nt2==c[1]&&nt3==c[2]&&nt5==c[3]&&nt7==c[4]&&nt0==c[0])
(sum+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt7++;
nt7=min(nt7,c[4]);
if(nt2==c[1]&&nt3==c[2]&&nt5==c[3]&&nt7==c[4]&&nt0==c[0])
(sum+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt2+=3;
nt2=min(nt2,c[1]);
if(nt2==c[1]&&nt3==c[2]&&nt5==c[3]&&nt7==c[4]&&nt0==c[0])
(sum+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt3+=2;
nt3=min(nt3,c[2]);
if(nt2==c[1]&&nt3==c[2]&&nt5==c[3]&&nt7==c[4]&&nt0==c[0])
(sum+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
}
}
}
}
}
for(int i=sz;i>=1;i--){
int tt=s[i]-'0';
for(int j=0;j<tt;j++){
if(j==0&&i==sz) continue;
for(int t2=0;t2<=c[1];t2++){
for(int t3=0;t3<=c[2];t3++){
for(int t5=0;t5<=c[3];t5++){
for(int t7=0;t7<=c[4];t7++){
for(int t0=0;t0<=c[0];t0++){
if(j==0)
{
int nt2=t2+st2,nt3=t3+st3,nt5=t5+st5,nt7=t7+st7,nt0=t0|st0;
nt2=min(nt2,c[1]),nt3=min(nt3,c[2]),nt5=min(nt5,c[3]),nt7=min(nt7,c[4]);
nt0=1;
(dp[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
if(j==2)
{
int nt2=t2+st2,nt3=t3+st3,nt5=t5+st5,nt7=t7+st7,nt0=t0|st0;
nt2=min(nt2,c[1]),nt3=min(nt3,c[2]),nt5=min(nt5,c[3]),nt7=min(nt7,c[4]);
nt2++;
nt2=min(nt2,c[1]);(dp[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
if(j==3)
{
int nt2=t2+st2,nt3=t3+st3,nt5=t5+st5,nt7=t7+st7,nt0=t0|st0;
nt2=min(nt2,c[1]),nt3=min(nt3,c[2]),nt5=min(nt5,c[3]),nt7=min(nt7,c[4]);
nt3++;
nt3=min(nt3,c[2]);(dp[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
if(j==4)
{
int nt2=t2+st2,nt3=t3+st3,nt5=t5+st5,nt7=t7+st7,nt0=t0|st0;
nt2=min(nt2,c[1]),nt3=min(nt3,c[2]),nt5=min(nt5,c[3]),nt7=min(nt7,c[4]);
nt2+=2;
nt2=min(nt2,c[1]);(dp[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
if(j==5)
{
int nt2=t2+st2,nt3=t3+st3,nt5=t5+st5,nt7=t7+st7,nt0=t0|st0;
nt2=min(nt2,c[1]),nt3=min(nt3,c[2]),nt5=min(nt5,c[3]),nt7=min(nt7,c[4]);
nt5++;
nt5=min(nt5,c[3]);(dp[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
if(j==6)
{
int nt2=t2+st2,nt3=t3+st3,nt5=t5+st5,nt7=t7+st7,nt0=t0|st0;
nt2=min(nt2,c[1]),nt3=min(nt3,c[2]),nt5=min(nt5,c[3]),nt7=min(nt7,c[4]);
nt2++;
nt3++;
nt2=min(nt2,c[1]);
nt3=min(nt3,c[2]);(dp[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
if(j==7)
{
int nt2=t2+st2,nt3=t3+st3,nt5=t5+st5,nt7=t7+st7,nt0=t0|st0;
nt2=min(nt2,c[1]),nt3=min(nt3,c[2]),nt5=min(nt5,c[3]),nt7=min(nt7,c[4]);
nt7++;
nt7=min(nt7,c[4]);(dp[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
if(j==8)
{
int nt2=t2+st2,nt3=t3+st3,nt5=t5+st5,nt7=t7+st7,nt0=t0|st0;
nt2=min(nt2,c[1]),nt3=min(nt3,c[2]),nt5=min(nt5,c[3]),nt7=min(nt7,c[4]);
nt2+=3;
nt2=min(nt2,c[1]);(dp[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
if(j==9)
{
int nt2=t2+st2,nt3=t3+st3,nt5=t5+st5,nt7=t7+st7,nt0=t0|st0;
nt2=min(nt2,c[1]),nt3=min(nt3,c[2]),nt5=min(nt5,c[3]),nt7=min(nt7,c[4]);
nt3+=2;
nt3=min(nt3,c[2]);(dp[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
}
}
}
}
}
if(j==0){
st0=1;
}
if(j==2){
st2++;
}
if(j==3){
st3++;
}
if(j==4){
st2+=2;
}
if(j==5){
st5++;
}
if(j==6){
st2++,st3++;
}
if(j==7){
st7++;
}
if(j==8){
st2+=3;
}
if(j==9){
st3+=2;
}
}
}
ll ans=0;
if(st2==c[1]&&st3==c[2]&&st5==c[3]&&st7==c[4]&&st0==c[0]) ans++;
for(int i=1;i<=sz;i++)
for(int t2=0;t2<=c[1];t2++){
for(int t3=0;t3<=c[2];t3++){
for(int t5=0;t5<=c[3];t5++){
for(int t7=0;t7<=c[4];t7++){
for(int t0=0;t0<=c[0];t0++){
if((t2==c[1]&&t3==c[2]&&t5==c[3]&&t7==c[4])||t0==1) (ans+=dp[i][t2][t3][t5][t7][t0])%=mod;
}
}
}
}
}
return ans;
}
void work1(){
f[0][0][0][0][0][0]=1;
for(int i=1;i<=25;i++){
for(int t2=0;t2<=c[1];t2++){
for(int t3=0;t3<=c[2];t3++){
for(int t5=0;t5<=c[3];t5++){
for(int t7=0;t7<=c[4];t7++){
for(int t0=0;t0<=c[0];t0++){
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt0=1;
(f[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt2++;
nt2=min(nt2,c[1]);
(f[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt3++;
nt3=min(nt3,c[2]);
(f[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt2+=2;
nt2=min(nt2,c[1]);
(f[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt5++;
nt5=min(nt5,c[3]);
(f[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt2++;
nt3++;
nt2=min(nt2,c[1]);
nt3=min(nt3,c[2]);
(f[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt7++;
nt7=min(nt7,c[4]);
(f[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt2+=3;
nt2=min(nt2,c[1]);
(f[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
{
int nt2=t2,nt3=t3,nt5=t5,nt7=t7,nt0=t0;
nt3+=2;
nt3=min(nt3,c[2]);
(f[i][nt2][nt3][nt5][nt7][nt0]+=f[i-1][t2][t3][t5][t7][t0])%=mod;
}
}
}
}
}
}
}
//cout<<f2[1][1]<<endl;
cout<<(Cal(R)-Cal(trans(L))+mod)%mod<<endl;
}
signed main()
{
cin>>n;
cin>>L>>R;
ll nn;
nn=n;
c[0]=1;
while(nn%2==0){
c[1]++;
nn/=2;
}
while(nn%3==0){
c[2]++;
nn/=3;
}
while(nn%5==0){
c[3]++;
nn/=5;
}
while(nn%7==0){
c[4]++;
nn/=7;
}
if(nn==1){
work1();
}else{
work2();
}
}
Details
/tmp/cc5v2Ymg.o: in function `cal(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >)': answer.code:(.text+0x21fd): relocation truncated to fit: R_X86_64_PC32 against symbol `d2' defined in .bss section in /tmp/cc5v2Ymg.o answer.code:(.text+0x2226): relocation truncated to fit: R_X86_64_PC32 against symbol `f2' defined in .bss section in /tmp/cc5v2Ymg.o answer.code:(.text+0x22b0): relocation truncated to fit: R_X86_64_PC32 against symbol `f2' defined in .bss section in /tmp/cc5v2Ymg.o answer.code:(.text+0x2380): relocation truncated to fit: R_X86_64_PC32 against symbol `d2' defined in .bss section in /tmp/cc5v2Ymg.o /tmp/cc5v2Ymg.o: in function `work2()': answer.code:(.text+0x2599): relocation truncated to fit: R_X86_64_PC32 against symbol `f2' defined in .bss section in /tmp/cc5v2Ymg.o answer.code:(.text+0x25d0): relocation truncated to fit: R_X86_64_PC32 against symbol `f2' defined in .bss section in /tmp/cc5v2Ymg.o /tmp/cc5v2Ymg.o: in function `main': answer.code:(.text.startup+0xf): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cc5v2Ymg.o answer.code:(.text.startup+0x3c): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cc5v2Ymg.o /tmp/cc5v2Ymg.o: in function `_GLOBAL__sub_I_n': answer.code:(.text.startup+0x252): relocation truncated to fit: R_X86_64_PC32 against symbol `v' defined in .bss section in /tmp/cc5v2Ymg.o answer.code:(.text.startup+0x265): relocation truncated to fit: R_X86_64_PC32 against symbol `mp' defined in .bss section in /tmp/cc5v2Ymg.o answer.code:(.text.startup+0x26e): additional relocation overflows omitted from the output collect2: error: ld returned 1 exit status