前言

依舊是固定的前言。
拿下了第四名，和第三名同分結果提交次數多了。
發現第三名是我的同學並且比我弱之後大膽猜測他使用的奇怪的方法。
結果看了他T3的代碼，的確如此，他居然轉移的時候只轉移前面和後面的 \(500\) 個，然後數據太水過了。
顯然是在模仿CCF，數據也太好了（確信。

話不多説，我的得分情況：90+100+20+0=210，第一題沒有做出來挺離譜的，所以我寫T2題解
接下來開始我們的正題

題目意思

你現在有兩種操作，一種是將你現在手持的數字加上 \(x_1\) 耗費 \(c_1\) 的價值，另一種是將手持的乘上 \(x_2\) 耗費 \(c_2\) 的價值，要你從 \(1\) 變到 \(N\) 的最小价值，如果不行就報告不可能。

題目思考

這是我在草稿紙上面的思路：
首先我們可以將多次的加合併為 \(+ tx_1\)，多次的乘合併為 \(\times x_2^t\)
我嘗試證明操作序列為 \(+ \times +\) 或者 \(\times + \times\)，但是發現不能證明，所以這説明他可能進行了若干次 \(+ \times\) 的操作，所以不妨設我們依次進行了 \(n_1\) 次 \(+\) 操作，\(m_1\) 次 \(\times\) 操作，\(n_2\) 次 \(+\) 操作，\(m_2\) 次 \(\times\) 操作，以此類推。
此時我們考慮他的最終數字，經過 \(n_1\) 次 \(+\) 操作後變為 \(1+n_1x_1\)，經過 \(m_1\) 次操作後變為 \((1+n_1x_1)x_2^{m_1}\)，經過 \(n_2\) 次 \(+\) 操作，\(m_2\) 次 \(\times\) 後變為

接下來式子就化的差不多了，我們去看經過這些操作時候他的代價是多少，經過 \(n_1\) 次 \(+\) 操作，\(m_1\) 次 \(\times\) 操作後，代價是 \(n_1c_1+m_1c_2\)，現在還看不出什麼，但經過 \(n_2\) 次 \(+\) 操作，\(m_2\) 次 \(\times\) 後，代價變為 \(n_1c_1+m_1c_2+n_2c_1+m_2c_2=(n_1+n_2)c_1+(m_1+m_2)c_2\) 然後觀察 \(c_1\) 前面的係數，發現 \((n_1+n_2)\) 就是最後變成的數字裏面，含有 \(x_1\) 的項前面的係數！觀察 \(c_2\) 的係數，發現 \((m_1+m_2)\) 就是最高次項的次數，也就是所謂的 \(t\)，所以正確思路就出來了。

思路

我們發現 \(x_2^{m_1+m_2}\le n\) 所以我們枚舉 \(m_1+m_2\) 的值，除非 \(x_2=1\) 這個值必然小於 \(64\)，所以首先我們特判 \(x_2\) 的值，接着我們對於每一個枚舉的 \(m_1+m_2\)，\(c_2\) 的貢獻已經固定了，所以我們要使 \(c_1\) 的貢獻儘量小，觀看式子 \(x_1x_2^t>x_1x_2^{t-1}\) 所以我們要讓 \(x_1x_2^t\) 的係數儘可能大，接着是 \(x_1x_2^{t-1}\) 的係數儘可能大，這樣就能讓係數之和儘可能小了，具體的可以嘗試藉助代碼理解，我就使用了 \(int128\) 存儲，不然可能炸掉。

代碼

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cmath>
#define ll __int128 

using namespace std;
const ll Inf=0x3f3f3f3f3f3f3f3f,N=1e5+9;
ll n,x,xx,c,cc,a[N],ans;

int main(){
    int garbage,T;
    cin>>garbage>>T;
    while(T--){
    	long long inputn,inputx,inputc,inputcc,inputxx;
    	cin>>inputn>>inputx>>inputc>>inputxx>>inputcc;
    	n=inputn;x=inputx;c=inputc;xx=inputxx;cc=inputcc;
        if(xx<=1){
			if(x==0){
				cout<<"-1\n";
				continue;
			}
        	if((n-1)%x==0) cout<<(long long)(c*(n-1)/x)<<endl;
        	else cout<<"-1\n";
        	continue;
		} 
		ll cnt=1;a[0]=1;ans=Inf;
		while(a[cnt-1]<=n) a[cnt]=a[cnt-1]*xx,cnt++;
		cnt--;
		for(int i=cnt;i>=0;i--){
			ll nn=n-a[i],nans=i*cc;
			if(nn<0) continue;	
			for(int j=i;j>=0;j--){
				if(a[j]>(n+x-1)/x) continue;
				if(nn>=x*a[j]){
					ll tmp=nn/(x*a[j]);
					nans+=tmp*c;
					nn%=(x*a[j]);
				}
			}
			if(nn!=0) continue;
			ans=min(ans,nans);
		}
		if(ans==Inf) cout<<"-1\n";
		else cout<<(long long)ans<<endl;
    }   
    return 0;
}

後記

剩下的就是這個題目的思考了，寫完了我仍然十分震撼我做出了這個題目，每一步彷彿都是機緣巧合，但是最後我還是死磕出來了，挺幸運的吧，如果下次沒有這麼幸運的話我還是希望我能通過我的努力把這種題目做出來，總結一下，以後遇到這種題目要願意去推式子，求價值，不要怕就好了。