Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <cstdio>
- #include <queue>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- vector <int> eu;
- vector < pair<int,int> > v[200010];
- char rj[200010];
- bool bio[200010];
- bool bio2[200010];
- int k;
- void bla(int pos){
- for(int j=0;j<200003;++j)
- if(v[j].size()%2==1){
- v[j].push_back(make_pair(200005,k));
- v[200005].push_back(make_pair(j,k));
- ++k;
- }
- }
- void euler(int pos){
- bio2[pos]=true;
- while(!v[pos].empty()){
- int x=v[pos][v[pos].size()-1].first;
- int y=v[pos][v[pos].size()-1].second;
- if(bio[y]==true){
- v[pos].pop_back();
- continue;
- }
- bio[y]=true;
- euler(x);
- eu.push_back(y);
- }
- }
- int n;
- int ax,bx,mx,ay,by,my;
- long long x1,y1;
- int t;
- int main(void){
- scanf("%d",&t);
- for(int p=0;p<t;++p){
- memset(bio,0,sizeof(bio));
- memset(bio2,0,sizeof(bio2));
- k=0;
- scanf("%d",&n);
- scanf("%lld%lld%d%d%d%d%d%d",&x1,&y1,&ax,&bx,&mx,&ay,&by,&my);
- v[x1].push_back(make_pair(y1+mx,k));
- v[y1+mx].push_back(make_pair(x1,k));
- ++k;
- for(int i=2;i<=n;++i){
- x1=(x1*ax+bx)%mx;
- y1=(y1*ay+by)%my;
- v[x1].push_back(make_pair(y1+mx,k));
- v[y1+mx].push_back(make_pair(x1,k));
- ++k;
- }
- for(int i=0;i<200003;++i)
- if(!v[i].empty() && !bio2[i]){
- eu.clear();
- bla(i);
- euler(i);
- bool x=0;
- for(int j=0;j<eu.size();++j){
- if(x) rj[eu[j]]='A';
- else rj[eu[j]]='B';
- x=!x;
- }
- }
- for(int i=0;i<n;++i)
- printf("%c",rj[i]);
- printf("\n");
- }
- return 0;}
Add Comment
Please, Sign In to add comment