Noble 的博客

Noble 的博客

♡虹蓝♡

题解 P5248 【[LnOI2019SP]快速多项式变换(FPT)】

posted on 2019-03-12 21:55:49 | under 题解 |

可以转换一下题目,发现题目相当于给定n-1(n<=100)种物品,放入一个背包内,使剩余空间最小。

贪心从大向小放就行了。

口胡一下为啥是对的。

首先f(m)=a0+k*m肯定是没毛病的。

由于“0<=ai<m",所以我们可以把km换成(k%m)m +( k/m * m^2).若k/m>m,则继续刚才的步骤。

这样我们虽然对数论和进制完全不开窍,也可以通过了。

差点没做出来签到题啊。

#include <iostream>
using namespace std;
#define reg register
const int kmaxn=100+5;
unsigned long long ans[kmaxn];
unsigned long long data[kmaxn];
long long m,f,cnt;
unsigned long long temp;
int main()
{
    ios::sync_with_stdio(false);
    cin>>m>>f;
    temp=1;
    data[0]=1;
    for(reg int i=1;i<100;++i,++cnt)
    {
        if(temp>f/m+1)
            break;
        temp*=m;
        data[i]=temp;
    }
    for(reg int i=cnt;i>=0;--i)
    {
        ans[i]=f/data[i];
        f-=ans[i]*data[i];
    }
    cout<<cnt+1<<endl;
    for(reg int i=0;i<=cnt;++i)
    {
        cout<<ans[i]<<' ';
    }
    cout<<endl;
    return 0;
}

不过也只做出来了签到题就是了QAQ