南京电信网站空间扩容,无锡大型网站设计公司,高端网站创建,辽宁建设工程信息网官网查询K - Let the Flames Begin
题意#xff1a;
n个人围成一个环#xff0c;编号分别是1~n#xff0c;从第一个人开始报数#xff0c;报道k的人被移除#xff0c;然后下一个人从1重新报#xff0c;一直这样进行。问第m给被移除的人报数是多少#xff1f; 一共T组数据…K - Let the Flames Begin
题意
n个人围成一个环编号分别是1~n从第一个人开始报数报道k的人被移除然后下一个人从1重新报一直这样进行。问第m给被移除的人报数是多少 一共T组数据所有组数据的min{m,k}的总和不会超过2e6
题解:
经典约瑟夫环约瑟夫环的模板
//从第一个开始报数数到k的将被杀掉
int josepus(int n,int k)
{int r0;for(int i2;in;i) r(rk)%i;return r1; //0~n-1 所以最后结果1
}
//第m个被杀掉的人
int josepus(int n,int m,int k)
{r(k-1)%(n-m1);for(int i2;im;i){r(rk)%(n-mi);}return r1;
}min{m,k}的总和不会超过2e6 当mk时m的总和不会超过2e6我们可以直接用约瑟夫环的模板复杂度O(m) 当mk时直接用模板会超时我们注意看公式(rk)%(n-mi);当k小时此时k可能远小于n因为n的范围可以达到1e18那么ans可能加上好几轮k都无法取模所有我们用乘法加速直接求出ansc*k(n-mi),求c的值这样可以加速运算
代码
#includebits/stdc.h
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,n) for(int i0;(i)(n);i)
#define rep1(i,n) for(int i1;(i)(n);i)
#define se secondusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int pii;
int dx[4] {-1,1,0,0},dy[4] {0,0,1,-1};
const ll mod2520;
const ll N2e510;int main(){iosint t;cint;int cc0;while(t--){ll n,m,k;cinnmk;ll ans0;if(k1) ansm;else{if(mk){ans(k-1)%(n-m1);for(int i2;im;i){ans(ansk)%(n-mi);}ans;}else{ans(k-1)%(n-m1);ll now1;ll t;while(nowm){/*ansc*k(n-mi)c((n-mi)-ans)/k*/t((n-mnow)-ansk-2)/(k-1);//向上取整if(nowtm){ans(ans(m-now)*k)%n;}else ans(anst*k)%(n-m(nowt));nowt;}ans;}}coutCase #cc: ansendl;}return 0;
}
