T1 种树
只需要运用一些小学奥数即可解决
首先需要知道的一点是将 \(p_i\) 质因数分解后得到 \(p_i = \prod\limits_{j = 1}^m a_j^{k_j}\) ，则有 \(\prod\limits_{i = 1}^{m} (k_i+1)\) 个因数
则最终就是把所有的都再乘起来
考虑 \(w\) 分解后能造成什么影响，依据乘法分配律发现我们要把 \(w\) 的质因数都分给最小的 \(k_i\) （包括 \(k_i\) 为 \(0\) 的情况）便可以做到答案最大
那么只需要开质因数种类数个堆维护最小值就可以了，代码也很好写
#include<bits/stdc++.h>
#define mod 998244353
#define N 10010
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int n,k,w,cnt[N],mx[N],prime[N],tot,a[N],id[N];
priority_queue<int,vector<int>,greater<int> >q[N];
inline void init(){
mx[0] = mx[1] = 1;
for(int i = 2;i<=N-10;i++){
if(!mx[i]) prime[++tot] = i,id[i] = tot,mx[i] = i;
for(int j = 1;j<=tot&&i*prime[j]<=N-10;j++){
mx[i*prime[j]] = prime[j];
if(i%prime[j]==0) break;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
init();
cin>>n>>k;
for(int i = 1;i<=n;i++){
cin>>a[i];
while(a[i]!=1){
cnt[id[mx[a[i]]]]++;
a[i]/=mx[a[i]];
}
for(int j = 1;j<=tot;j++)
if(cnt[j]){
q[j].emplace(cnt[j]);
cnt[j] = 0;
}
}
while(k!=1){
if(q[id[mx[k]]].size()<n){
q[id[mx[k]]].emplace(1);
k/=mx[k];
continue;
}
int u = q[id[mx[k]]].top();q[id[mx[k]]].pop();
u++;
q[id[mx[k]]].emplace(u);
k/=mx[k];
}
int ans = 1;
for(int i = 1;i<=tot;i++){
while(q[i].size()){
ans = 1ll*ans*(q[i].top()+1)%mod;
q[i].pop();
}
}
cout<<ans;
return 0;
}
T2 汪了个汪
题解区第一篇的人类智慧太强了，我就不献丑了，正解是图论，不过不好写
反正我也只会那个人类智慧
#include<bits/stdc++.h>
#define N 4010
using namespace std;
int n,t,a[N][N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>t;
for(int i = 1;i<=n;i++){
int len = 1,st = (i&1)?(2*n-i+1)/2:(i>>1);
for(int j = 1;j<=i;j++){
cout<<st<<" ";
if(j&1) st+=len;
else st-=len;
len++;
}
cout<<"\n";
}
return 0;
}
T3 挑战 NPC IV
这道题其实并不是很难想前面 \(52\) 分的，只需要考虑到对于 \(k = 2\) 时一定是与 \(k=1\) 的答案一样的就能拿到 \(32\) 分
对于 \(52\) 分来说，你只需要发现 \(n\ge 29\) 时 \(k\le 10^{18}\) 的答案都一样就行
要拿到这几分，首先需要知道一个位置会被计算 \(i\times (n-i+1)\) 次，那么最小的排列就是大的放两端小的放中间
然后你可以发现对于对称的两个位置来说的贡献是一样的，那么就可以交换而使答案不变，所以第一个结论成立
又因为对于位置的排列交换之后会有非常多种，那么在计算一通后就可以发现第二个性质
计算过程去翻题解应该有
其实第二个并不需要花费 \(\mathcal O(n\log n)\) 的时间来模拟排列，只需要大力推导一个式子就可以 \(\mathcal O(\log n)\) 求出答案
那我们剩下的只有 \(n \le 28\) 时的情况了
然后就是一个极为炸裂的 \(dp\) ，对于这个逆天玩意，大家还是看题解吧 我不太懂
所以我写这么多有啥用
#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int n,k,dp[15][8][5][3][2][6000],inv2 = (mod+1)>>1,inv6 = (mod+1)/6,cnt[70],fac[20];
int dfs(int x,int t1,int t2,int t3,int t4,int t5,int y){
if(y<0||t1<0||t2<0||t3<0||t4<0||t5<0) return 0;
if(!y) return t1||t2||t3||t4||t5?0:1;
int &ans = dp[t1][t2][t3][t4][t5][y];
if(~ans) return ans;
ans = 0;
int p = t1+t2+t3+t4+t5;
p = p*(x-p+1);
ans+=dfs(x,t1-1,t2,t3,t4,t5,y-p);
ans+=dfs(x,t1,t2-1,t3,t4,t5,y-2*p);
ans+=dfs(x,t1,t2,t3-1,t4,t5,y-3*p);
ans+=dfs(x,t1,t2,t3,t4-1,t5,y-4*p);
ans+=dfs(x,t1,t2,t3,t4,t5-1,y-5*p);
return ans;
}
inline int calc(int x,int y){
x%=mod;y%=mod;
int ans = (x+1)*y%mod*(y+1)%mod*inv2%mod;
ans-=y*(y+1)%mod*(2*y+1)%mod*inv6%mod;
return (ans+mod)%mod;
}
inline int getans(int x){
int y = (x>>1),ans = 0;
for(int i = 0;i<60;i++)
cnt[i+1] = x>>i;
for(int i = 1;i<60;i++)
cnt[i]-=cnt[i+1];
if(x&1){
ans = (y+1)%mod*((x-y+mod)%mod)%mod;
cnt[1]--;
}
for(int i = 1;i<=60;i++){
int t = cnt[i]>>1;y-=t;
ans = (ans+2*(calc(x,y+t)-calc(x,y)+mod)%mod*i%mod)%mod;
if(cnt[i]&1){
ans = (ans+y%mod*((x-y+1+mod)%mod)%mod*i%mod)%mod;
ans = (ans+y%mod*((x-y+1+mod)%mod)%mod*(i+1)%mod)%mod;
cnt[i+1]--;y--;
}
}
for(int i = 0;i<60;i++)
cnt[i+1] = x>>i;
for(int i = 1;i<60;i++)
cnt[i]-=cnt[i+1];
return ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
fac[0] = 1;
for(int i = 1;i<=15;i++)
fac[i] = fac[i-1]*i;
int T;cin>>T;
while(T--){
cin>>n>>k;
int x = getans(n);
if(n>28){
cout<<x<<"\n";
continue;
}
for(int i = 1;i<=5;i++)
k = (k-1)/fac[cnt[i]]+1;
memset(dp,0xff,sizeof(dp));
while(1){
int y = dfs(n,cnt[1],cnt[2],cnt[3],cnt[4],cnt[5],x);
if(y>=k){
cout<<x<<"\n";
break;
}
k-=y;x++;
}
}
return 0;
}
T4 四暗刻单骑
不懂麻将
好吧这题咋都不好拿分，不说了
标签：cnt,231112,int,ans,洛谷,mod,mx,模拟,define From： https://www.cnblogs.com/cztq/p/17827672.html