2020-2021:teams:wangzai_milk:20200713比赛记录
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:20200713比赛记录 [2020/07/15 00:37] infinity37 [比赛总结与反思] |
2020-2021:teams:wangzai_milk:20200713比赛记录 [2020/07/16 15:16] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 698: | 行 698: | ||
| } | } | ||
| </code></hidden> | </code></hidden> | ||
| + | \\ | ||
| + | |||
| + | ==== J - Just Shuffle ==== | ||
| + | |||
| + | 给一个置换 $A$ 和大质数 $k$，求置换 $P$ 使得 $P^k = A$。 | ||
| + | |||
| + | 求出 $A$ 的每个循环节，因为 $k$ 是个大质数，所以 $P$ 每个循环节作 $k$ 次方都不会分裂，于是 $P$ 的循环节和 $A$ 的循环节是一样的，只是向右平移了 $k$ 对循环节长度的逆元个长度。 | ||
| + | |||
| + | <hidden code> <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ALL(x) (x).begin(),(x).end() | ||
| + | #define ll long long | ||
| + | #define ull unsigned long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #define mp_ make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define pg PermutationGroup | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
| + | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
| + | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 1e5+5; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | inline ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);} | ||
| + | inline ll lcm(ll a,ll b) {return a*b/gcd(a,b);} | ||
| + | ll extgcd(ll a,ll b,ll& u,ll& v) | ||
| + | { | ||
| + | ll d; | ||
| + | if(b==0){ | ||
| + | d = a; | ||
| + | u=1,v=0; | ||
| + | }else { | ||
| + | d = extgcd(b,a%b,v,u); | ||
| + | v -= a/b*u; | ||
| + | }return d; | ||
| + | } | ||
| + | int n,k,vis[maxn]; | ||
| + | int P[maxn],ans[maxn],a[maxn],tmp[maxn],ttt[maxn]; | ||
| + | int main() | ||
| + | { | ||
| + | //fastio(); | ||
| + | scanf("%d%d",&n,&k); | ||
| + | rep(i,1,n) scanf("%d",&a[i]); | ||
| + | rep(i,1,n)if(!vis[i]){ | ||
| + | vis[i] = 1; | ||
| + | vector<int> pos; | ||
| + | int u = a[i],len = 1;pos.pb(i); | ||
| + | while(u!=i){ | ||
| + | len++; | ||
| + | vis[u] = 1;pos.pb(u); | ||
| + | u = a[u]; | ||
| + | } | ||
| + | ll x,y; | ||
| + | extgcd(k,len,x,y); | ||
| + | x = (x%len+len)%len; | ||
| + | rep(i,1,len){ | ||
| + | ans[pos[i-1]] = pos[(i-1+x)%len]; | ||
| + | } | ||
| + | } | ||
| + | rep(i,1,n) printf("%d ",ans[i]); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> </hidden> | ||
| \\ | \\ | ||
| ==== K - Keyboard Free ==== | ==== K - Keyboard Free ==== | ||
| 行 747: | 行 815: | ||
| C题一开始想错了耽误了一些时间，想到了对的实现还很艰难呜呜呜呜该多写难题代码了。FWT这个有点可惜，感觉要多做一些FWT题了。 ——Infinity37 | C题一开始想错了耽误了一些时间，想到了对的实现还很艰难呜呜呜呜该多写难题代码了。FWT这个有点可惜，感觉要多做一些FWT题了。 ——Infinity37 | ||
| + | |||
| + | 和上一场一样都是一个题卡了几个小时？（以后要试着跳出来。 ——_wzx27 | ||
2020-2021/teams/wangzai_milk/20200713比赛记录.1594744645.txt.gz · 最后更改: 2020/07/15 00:37 由 infinity37
