今天寫了幾道題目
最近，一年級學生馬克西姆學習了科拉茲猜想，但他在講課時沒有太注意，所以他認為猜想中提到了以下過程：
有一個變量 $$$x$$$ 和一個常數 $$$y$$$ 。下面的操作要執行 $$$k$$$ 次：
- 將 $$$x$$$ 增加 $$$1$$$ ，然后
- 當數字 $$$x$$$ 能被 $$$y$$$ 整除時，再除以 $$$y$$$ 。
請注意，這兩個操作都是在一次操作中依次進行的。
例如，如果數字 $$$x = 16$$$ 、 $$$y = 3$$$ 和 $$$k = 2$$$ ，那么經過一次運算后， $$$x$$$ 變成了 $$$17$$$ ，而經過另一次運算后， $$$x$$$ 變成了 $$$2$$$ ，因為加一后， $$$x = 18$$$ 可以被 $$$3$$$ 整除兩次。
鑒于初始值為 $$$x$$$ 、 $$$y$$$ 和 $$$k$$$ ，馬克西姆想知道 $$$x$$$ 的最終值是多少。
思路是先湊到y的倍數，在除y，考慮到時間的問題，所以基于二分的思想設置了一個s每次對自己平方再判斷能不能整除，復雜度從n降到了logn，一直除到a<b,再湊到a等于b，再除就是1，那么就是對剩下的c的部分對（b-1）取余再加一即為答案。
#include<bits/stdc++.h>
#include<algorithm>
#define ll long long
#define max_int 2147483647
#define max_ll 9223372036854775807
using namespace std;
int main()
{ios::sync_with_stdio(false);cin.tie(0);int all;cin>>all;while(all--){ll a,b,c;cin>>a>>b>>c;int bo=1;while(c){ll yu=b-a%b;ll s=b,s2=b*b;if(yu<=c){c-=yu;a+=yu;}else{cout<<a+c<<endl;bo=0;break;}while(a%b==0){s=b;while(a%s==0){s2=s;s*=s;}a/=s2;}if(a<b){if(c>=b-a){c-=b-a;}else{cout<<a+c<<endl;bo=0;break;}if(c==0){cout<<'1'<<endl;bo=0;break;}cout<<c%(b-1)+1<<endl;bo=0;break;}//if(bo) cout<<a<<endl;//else break;}if(bo) cout<<a<<endl;}return 0;
}
關鍵在組合數的拆分和前綴和處理以及取模的問題。
#include<bits/stdc++.h>
#define ll long long
#define max_int 2147483647
#define max_ll 9223372036854775807
using namespace std;
vector<vector<int>>q(2001,vector<int>(2001));
vector<vector<int>>p(2001,vector<int>(2001));
void solve(int k){q[1][1]=1;for(int i=0;i<=2000;++i){q[i][0]=1;}for(int i=2;i<=2000;i++){for(int j=1;j<=i;j++){q[i][j]=(q[i-1][j]+q[i-1][j-1])%k;}}for(int i=2;i<=2000;i++){for(int j=1;j<=i;j++){p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1];if(q[i][j]==0) p[i][j]+=1;}p[i][i+1]=p[i][i];}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t,k,n,m;cin>>t>>k;solve(k);for(int i=0;i<t;++i){cin>>n>>m;if(m>n) m=n;cout<<p[n][m]<<endl;}return 0;
}
)
