2020-2021:teams:namespace:牛客多校第二场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:namespace:牛客多校第二场 [2020/07/17 12:00] great_designer [K] |
2020-2021:teams:namespace:牛客多校第二场 [2020/07/17 12:24] (当前版本) great_designer [E] |
||
|---|---|---|---|
| 行 727: | 行 727: | ||
| printf("%d ",ans[i]); | printf("%d ",ans[i]); | ||
| } | } | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | =====J===== | ||
| + | |||
| + | 对给定置换A开k次方，k是个大素数。 | ||
| + | |||
| + | 由群论知，对大素数k，k次方运算是一一映射，所以实质是个求数论倒数的运算。 | ||
| + | |||
| + | 由于模不是素数，用费马欧拉定理不方便，只能改用一次不定方程的扩展来求逆。 | ||
| + | |||
| + | <hidden> | ||
| + | <code C++> | ||
| + | |||
| + | #include<stdio.h> | ||
| + | |||
| + | #include<vector> | ||
| + | |||
| + | using namespace std; | ||
| + | |||
| + | long long extgcd(long long a,long long b,long long& u,long long& v) | ||
| + | { | ||
| + | long long 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[100005]; | ||
| + | int P[100005],ans[100005],a[100005],tmp[100005],ttt[100005]; | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | scanf("%d%d",&n,&k); | ||
| + | int i; | ||
| + | for(i=1;i<=n;i++) | ||
| + | { | ||
| + | scanf("%d",&a[i]); | ||
| + | } | ||
| + | for(i=1;i<=n;i++) | ||
| + | { | ||
| + | if(!vis[i]) | ||
| + | { | ||
| + | vis[i] = 1; | ||
| + | vector<int> pos; | ||
| + | int u = a[i],len = 1;pos.push_back(i); | ||
| + | while(u!=i) | ||
| + | { | ||
| + | len++; | ||
| + | vis[u] = 1;pos.push_back(u); | ||
| + | u = a[u]; | ||
| + | } | ||
| + | long long x,y; | ||
| + | extgcd(k,len,x,y); | ||
| + | x = (x%len+len)%len; | ||
| + | int j; | ||
| + | for(j=1;j<=len;j++) | ||
| + | { | ||
| + | ans[pos[j-1]] = pos[(j-1+x)%len]; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | for(i=1;i<=n;i++) | ||
| + | { | ||
| + | printf("%d ",ans[i]); | ||
| + | } | ||
| + | return 0; | ||
| } | } | ||
2020-2021/teams/namespace/牛客多校第二场.1594958452.txt.gz · 最后更改: 2020/07/17 12:00 由 great_designer
