Educational Codeforces Round 84 (Rated for Div. 2)

D: Infinite Path

【题意】：定义infinite path: i , p[i], p[p[i]], p[p[p[i]]] ......中所有颜色都相同，那么它就是一条infinite path。即c[i] = c[p[i]] = c[p[p[i]]] = ......。定义：c = a × b,c[i] = b[a[i]]。求最小的k满足 (p^k(p×...×p)) 中存在至少一个infinite path。

分析：首先我们应该知道如果存在一个i = p[i]的话或者所有c[i]都相等的话是肯定满足的，那么k就等于1。否则的话它就是一个置换群。首先求出所有环的长度，可以用dfs处理。求出环的长度后，我们只需枚举环的因子，看看所有因子的倍数在环中的颜色是否相同，如果全都相同，那么就可以更新答案。

#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1);
int gcd(int a,int b)    { return b == 0 ? a : gcd(b, a % b); }

int p[maxn], c[maxn], n;
int vis[maxn];
vector<int> path;
void dfs(int now, int val)
{
    vis[val] = 1;
    if(now == val)  return;
    path.push_back(val);
    dfs(now, p[val]);
}

int main()
{
    int t; scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        int ok = 0, flag = 1;
        for(int i = 1; i <= n; ++i){
            vis[i] = 0;
            scanf("%d", &p[i]);
            if(i == p[i])   ok = 1;
        }
        for(int i = 1; i <= n; ++i){
            scanf("%d", &c[i]);
            if(i > 1 && c[i] != c[i-1]) flag = 0;
        }
        if(ok || flag)  puts("1");
        else{
            int ans = inf;
            for(int i = 1; i <= n; ++i){
                if(vis[i])  continue;
                vis[i] = 1;
                path.clear();   path.push_back(i);      //path记录一个置换群的长度
                dfs(i, p[i]);   
                for(int j = 1; j <= path.size(); ++j){  //枚举环的长度的因子
                    if(path.size() % j)     continue;
                    for(int k = 0; k < j; ++k){
                        int ok = 1;
                        for(int z = k; z < path.size(); z += j){
                            if(c[path[k]] != c[path[z]]){
                                ok = 0;
                                break;
                            }
                        }
                        if(ok)  ans = min(ans, j);
                    }
                }
            }
            printf("%d
", ans);
        }
    }
}

【分析】：首先 i = n时，只有n个0到n个9符合。即答案为10。根据这个我们用组合数学的知识想一想，首先设相等的长度为i，那么它的值能取0 ~ 9中(C_{10}^{1})个数，与他相邻的必须与他不同取(C_{9}^{1})个数。如果那个块在数字的连个边缘，那么它的贡献就是：(C_{10}^{1} * C_{9}^{1} * 10 ^ {n - i - 1} * 2)，如果在中间那么它的贡献就是：(C_{10}^{1} * C_{9}^{1} * C_{9}^{1} * (n - i - 2 + 1) * 10 ^ {n - i - 2})，其中(n - i - 2 + 1)表示在n - 2中取长度为 i 的连续长度的个数。

#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f, mod =  998244353;
const double eps = 1e-6, pi = acos(-1);
int gcd(int a,int b)    { return b == 0 ? a : gcd(b, a % b); }

int n;
LL qpow(LL a, LL b)
{
    //if(b < 0)   return 0;
    LL ans = 1;
    while(b){
        if(b & 1)   ans = (ans * a) % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int main()
{
    cin >> n;
    //只要那一段属于就可以了，不用管别的段是不是也有长度为i的段
    for(int i = 1; i <= n; ++i){
        if(i == n)  printf("10 ");
        else if(i == n-1)   printf("180 ");
        else{
            LL ans = (18 * qpow(10, n - i) % mod + 81 * qpow(10, n - i - 1) * (n - i - 1) % mod) % mod;
            printf("%lld ",ans);
        }
    }
    puts("");
    //system("pause");
}