QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#239692 | #7687. Randias Permutation Task | ucup-team1631# | WA | 0ms | 14136kb | C++20 | 2.9kb | 2023-11-04 22:30:09 | 2023-11-04 22:30:10 |
Judging History
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'