yicongli

Gym 313459H

Jan 24th, 2021
582
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=61;
  17.  
  18. ll F[N][N][N*N];
  19. bool vis[N][N][N*N];
  20.  
  21. ll f(int n,int c,int k){
  22.     if(!n && !k)return 1;
  23.     if(!n || k<0)return 0;
  24.     if(vis[n][c][k])return F[n][c][k];
  25.     vis[n][c][k]=1;
  26.     return F[n][c][k]=f(n-1,c,k-c)+f(n-1,c+1,k);
  27. }
  28.  
  29. void print(int n,int c,int k,ll x){
  30.     if(!n)return ;
  31.     if(x<f(n-1,c,k-c)){
  32.         putchar('A');
  33.         print(n-1,c,k-c,x);
  34.     }
  35.     else {
  36.         putchar('B');
  37.         print(n-1,c+1,k,x-f(n-1,c,k-c));
  38.     }
  39. }
  40.  
  41. int main(){
  42.     // freopen(".in","r",stdin);
  43.     // freopen(".out","w",stdout);
  44.     int n,k;r(n),r(k);
  45.     ll ans=f(n,0,k);
  46.     if(ans&1)print(n,0,k,ans>>1);
  47.     else {
  48.         print(n,0,k,(ans>>1)-1);
  49.         puts("");
  50.         print(n,0,k,ans>>1);
  51.     }
  52.     puts("");
  53.     return 0;
  54. }
RAW Paste Data