Pagini recente » Cod sursa (job #1256540) | Cod sursa (job #576330) | Cod sursa (job #1603746) | Cod sursa (job #1146809) | Cod sursa (job #1208547)
#include <fstream>
#include <bitset>
#define XMAX 1005
#define YMAX 1005
#define MMAX 666740
using namespace std;
int n,m,x,y,modx,mody,offsetx,offsety;
inline int x_next(int x)
{
return (x*x+offsetx)%modx;
}
inline int y_next(int y)
{
return (y*y+offsety)%mody;
}
long long int ans[MMAX];
int dist[XMAX][YMAX]; //Distanta de la (i,j) pana la (x,y) (in noduri)
bitset<YMAX> viz[XMAX];
int calc_dist(int x,int y)
{
if(viz[x][y])
return dist[x][y];
viz[x][y]=1;
int dist_next=calc_dist(x_next(x),y_next(y));
if(!dist_next)
return 0;
dist[x][y]=dist_next+1;
return dist[x][y];
}
long long int after[XMAX][YMAX]; //Cati roboti suplementari ajung la pozitia (i,j) dupa prima mutare
int main()
{
ifstream cin("robotei.in");
ofstream cout("robotei.out");
cin>>n>>m>>x>>y>>modx>>mody>>offsetx>>offsety;
if(x>=n || x<0 || y>=n || y<0){
cout<<"0 "<<(1ll*n*n)<<'\n';
cin.close();
cout.close();
return 0;
}
if(x>=modx || y>=mody){
cout<<"0 "<<(1ll*n*n-1)<<'\n';
cout<<"1 1\n";
cin.close();
cout.close();
return 0;
}
//Acum avem o matrice de modx pe mod y
viz[x][y]=1;
dist[x][y]=1;
for(int i=0;i<modx;i++)
for(int j=0;j<mody;j++)
calc_dist(i,j);
//Acum graful arata asa:
//dist[i][j] = 0 <=> Daca de la (i,j) nu se poate ajunge la (x,y)
//Altfel, e distanta de la (i,j) la (x,y) (in noduri)
for(int i=0;i<modx;i++)
for(int j=0;j<mody;j++)
after[x_next(i)][y_next(j)]+=((n-i-1ll)/modx+1ll)*((n-j-1ll)/mody+1ll)-1;
int per=dist[x_next(x)][y_next(y)];
if(!per){
for(int i=0;i<modx;i++)
for(int j=0;j<mody;j++)
if(dist[i][j] && dist[i][j]<=m)
ans[1]+=(after[i][j]+1);
else
ans[0]+=(after[i][j]+1);
for(int i=0;i<=m;i++)
if(ans[i])
cout<<i<<' '<<ans[i]<<'\n';
cin.close();
cout.close();
return 0;
}
//cout<<per<<'\n';
m++; //Numarul de celule
for(int i=0;i<modx;i++)
for(int j=0;j<mody;j++)
if(dist[i][j]){
if(dist[i][j]<=m){
int cate=(m-dist[i][j])/per+1;
ans[cate]++;
}
else
ans[0]++;
}
else
ans[0]++;
m--;
for(int i=0;i<modx;i++)
for(int j=0;j<mody;j++)
if(dist[i][j]){
if(dist[i][j]<=m){
int cate=(m-dist[i][j])/per+1;
ans[cate]+=(after[i][j]);
}
else
ans[0]+=after[i][j];
}
else
ans[0]+=after[i][j];
for(int i=0;i<=m;i++)
if(ans[i])
cout<<i<<' '<<ans[i]<<'\n';
cin.close();
cout.close();
return 0;
}