题解 P5248 【[LnOI2019SP]快速多项式变换(FPT)】
_虹_
2019-03-12 21:55:49
可以转换一下题目，发现题目相当于给定n-1（n<=100）种物品,放入一个背包内，使剩余空间最小。
贪心从大向小放就行了。
口胡一下为啥是对的。
首先f(m)=a0+k*m肯定是没毛病的。
由于“0<=ai<m"，所以我们可以把k*m换成(k%m)*m +( k/m * m^2).若k/m>m，则继续刚才的步骤。
这样我们虽然对数论和进制完全不开窍，也可以通过了。
~~差点没做出来签到题啊。~~
```cpp
#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~~