QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#239692#7687. Randias Permutation Taskucup-team1631#WA 0ms14136kbC++202.9kb2023-11-04 22:30:092023-11-04 22:30:10

Judging History

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

  • [2023-11-04 22:30:10]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:14136kb
  • [2023-11-04 22:30:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(A) A.begin(),A.end()
#define rep(i, n) for (ll i = 0; i < (ll) (n); i++)
bool DEB = 1;
const ll mod = 1e9+7;
vector<vll> P(2e5 + 4);
vector<ll> TPOW(2e5 + 4, 1);


vector<ll> fact, factinv, inv;
void prenCkModp(ll n) {
    fact.resize(n + 5);
    factinv.resize(n + 5);
    inv.resize(n + 5);
    fact[0] = fact[1] = 1;
    factinv[0] = factinv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < n + 5; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
        inv[i] = (mod - ((inv[mod % i] * (mod / i)) % mod) % mod + mod) % mod;
        factinv[i] = (factinv[i - 1] * inv[i]) % mod;
    }
}
ll nCk(ll n, ll k) {
    if (n < k || k < 0) return 0;
    return (fact[n] * ((factinv[k] * factinv[n - k]) % mod) % mod) % mod;
}


void init() {
    prenCkModp(2e5 + 2);
}

ll facttoll(vll &A){
    ll N=A.size();
    ll res=0;
    ll b=1;
    for(ll a=N-1;a>=0;a--){
        res+=A[a]*b;
        b*=(N-a);
    }
    return res;
}
ll lltofact(ll n){
    return 0;
}

string pmtostr(vll &A){
    string S('A',A.size()*2);
    rep(j,A.size()){
        S[j*2]=char('a'+A[j]/26);
        S[j*2+1]=char('a'+A[j]%26);
    }
    return S;
}

void solve() {
    ll N,M;
    cin>>N>>M;
    vector<vll> A(M,vll(N));
    rep(i,M){
        rep(j,N)cin>>A[i][j],A[i][j]--;
    }
    if(N<=8){
        unordered_map<string,ll> P;
        vll V(N);
        rep(i,N)V[i]=i;
        ll cnt=0;
        vector<vll> PM;
        do{
            P[pmtostr(V)]=cnt;
            PM.push_back(V);
            cnt++;
        }while(next_permutation(all(V)));
        vector<bool> US(cnt,0);
        rep(i,M){
            US[P[pmtostr(A[i])]]=1;
            rep(j,cnt){
                if(!US[j])continue;
                vll NV(N);
                rep(k,N){
                    NV[k]=PM[j][A[i][k]];
                }
                US[P[pmtostr(NV)]]=1;
            }
        }
        ll an=0;
        rep(j,cnt)if(US[j])an++;
        cout<<an%mod<<endl;
    }
    else{
        unordered_set<string> S; 
        ll cnt=0;
        rep(bit,1<<M){
            if(bit==0)continue;
            vll V={-1};
            rep(j,M){
                if(bit&(1<<j)){
                    if(V.back()==-1){
                        V=A[j];
                    }
                    else{
                        vll NV(N);
                        rep(i,N){
                            NV[i]=V[A[j][i]];
                            cnt++;
                        }
                        V=NV;
                    }
                }
            }
            S.insert(pmtostr(V));
        }
        //cout<<cnt<<endl;
        ll an=S.size();
        cout<<an%mod<<endl;
    }
}

int main() {

    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    init();
    solve();
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 14136kb

input:

5 4
1 2 3 4 5
5 1 3 4 2
3 4 1 5 2
5 2 4 1 3

output:

20

result:

wrong answer 1st numbers differ - expected: '8', found: '20'