QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#195179#4937. Permutation TransformationbruhWA 6ms6448kbC++204.0kb2023-10-01 01:47:562023-10-01 01:47:57

Judging History

你现在查看的是最新测评结果

  • [2023-10-01 01:47:57]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:6448kb
  • [2023-10-01 01:47:56]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef __int128 Int;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef pair<ll, ii> iii;
typedef unordered_map<ll, ll> unmap;

template<typename T> using pqmax = priority_queue<T>;
template<typename T> using pqmin = priority_queue<T, vector<T>,greater<T>>;
template<typename T> using oset = tree<T, null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define fi first
#define se second
#define sz size()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define lg(n) (ll)__lg(n)
#define btpc __builtin_popcount

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define FOR(i,a,b) for(ll i = a; i <= b; i ++)
#define REP(i,a,b) for(ll i = a; i < b; i ++)
#define FORD(i,a,b) for(ll i = a; i >= b; i --)
#define FORS(i,a,b,c) for(ll i = a; i <= b; i += c)
#define FORDS(i,a,b,c) for(ll i = a; i >= b; i -= c)
#define FORA(x,a) for(auto x: a)
#define FORAA(l,r,a) for(auto [l, r]: a)

#define EL cerr << endl;
#define DEBUGN(a) cerr << a << endl;
#define DEBUGA(a, n) FOR (i, 1, n) cerr << a[i] << " "; cerr << endl;
#define DEBUG_AOP(a, n) FOR (i, 1, n) cerr << a[i].fi << " " << a[i].se << endl;  
#define DEBUG_A2D(a, n, m) FOR (i, 1, n) {FOR (j, 1, m) cerr << a[i][j] << " "; cerr << endl;}
#define DEBUG cerr << "shut the fuck up please :3" << endl;

#define YES cout << "YES\n"; return;
#define NO cout << "NO\n"; return;
 
template<class X, class Y> bool mimi(X &x, const Y &y) {if(x>y){x=y;return 1;}return 0;}
template<class X, class Y> bool mama(X &x, const Y &y) {if(x<y){x=y;return 1;}return 0;}
istream &operator >> (istream &st, Int &a) {string s;a=0;st>>s;bool g=1;REP(i,0,s.sz){if(i==0&&s[i]=='-'){g = 0;continue;}a=a*10+s[i]-'0';}if(!g)a=-a;return st;}
ostream &operator << (ostream &st, const Int &a) {Int t=a;if(t==0){st<<0;return st;}if(t<0){st<<'-';t=-t;}string b;while(t!=0){b.pb((t%10+'0'));t/=10;}reverse(all(b));st<<b;return st;}

const ll nom = 2;
const ll base[] = {577, 677, 877, 977};
const ll mod[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277};
const ii dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

const ll INF = 1e18;
const ll N = 1e6 + 5;
const ll T = 4*N - 3;
const ll M = 998244353;

ll n;
ll a[N], vst[N];
map<ll, ll> m;

ll l2(ll n) {
    ll res = 0;
    while ((n % 2) == 0) {
        n /= 2;
        res ++;
    }
    return res;
}

ll findCycle(ll pos) {
    ll cycle = 0, now = pos;
    while (a[now] >= 0) {
        cycle ++;
        ll nxt = a[now];
        a[now] = -1;
        vst[now] = 1;
        now = nxt;
    }
    return cycle;
}

void solve(ll testID) {
    cin >> n;
    FOR (i, 1, n) cin >> a[i];
    
    ll cnt = 0;
    FOR (i, 1, n) {
        if (vst[i]) continue;

        ll cycle = findCycle(i);
        cnt = max(cnt, l2(cycle));
        while ((cycle % 2) == 0) cycle /= 2;
        if (cycle == 1) continue;
        
        ll repeat = 1, cur = 2;
        while (cur != 1) {
            cur = (cur * 2) % cycle;
            repeat ++;
        }

        FOR (p, 2, sqrt(repeat)) {
            if (repeat % p != 0) continue;

            ll cnt = 0;
            while ((repeat % p) == 0) {
                cnt ++;
                repeat /= p;
            }
            m[p] = max(m[p], cnt);
        }
        if (repeat > 1) m[repeat] = 1;
    }

    ll res = 1;
    FORAA (l, r, m) {
        while (r > 0) {
            res = (res * l) % M;
            r --;
        }
    }
    res = (res + cnt) % M;
    cout << res;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int test = 1;
    // cin >> test;
    FOR (i, 1, test) solve(i);
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5540kb

input:

5
3 5 1 2 4

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5588kb

input:

8
7 5 1 6 8 2 3 4

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5600kb

input:

1
1

output:

1

result:

ok single line: '1'

Test #4:

score: -100
Wrong Answer
time: 6ms
memory: 6448kb

input:

100000
20864 34918 58550 1465 75674 30743 27235 88900 47488 50029 46054 84871 20330 72228 16506 44561 92519 97750 82891 60324 90508 39290 24663 38077 90189 30671 95476 64027 70888 90749 22566 8525 33675 16635 23392 97636 35788 89625 41966 78051 94034 15407 26545 83799 2233 10873 56946 71566 19045 44...

output:

404859186

result:

wrong answer 1st lines differ - expected: '216333199', found: '404859186'