QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#242850#7687. Randias Permutation TaskhHap#TL 1ms5476kbC++202.1kb2023-11-07 17:49:442023-11-07 17:49:45

Judging History

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

  • [2023-11-07 17:49:45]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:5476kb
  • [2023-11-07 17:49:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N=362880+10;
int dp[181][N];
int p[180];
int a[181][181];
int b[180];
int n,m;
map<vector<int>, int> ccc;

void dfs(int u,int c[])
{
    if(u>m) return;
    int e[181];
    for(int i=1;i<=n;i++) e[i]=c[i];
    if(c[1])
    {
        for(int i=1;i<=n;i++)
        {
            c[i]=a[u][c[i]];
        }
    }
    else
        for(int i=1;i<=n;i++) c[i]=a[u][i];
    vector<int>tmp;
    for(int i=1;i<=n;i++) tmp.push_back(c[i]);
    ccc[tmp]++;

    dfs(u+1,e);
    dfs(u+1,c);
}

void solve()
{
    cin>>n>>m;
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++) cin>>a[i][j];
    }
    for(int i=1;i<=n;i++) p[i]=i;

    if(m>180)
    {
        map<int, int> mp;
        map<string,int> val;
        int r=0;
        do{
            r++;
            string tmp;
            for(int i=1;i<=n;i++) tmp+='0'+p[i];
            val[tmp]=r;
        }while(next_permutation(p+1,p+1+n));

        for(int i=1;i<=m;i++)
        {
            int rr=0;
            for(int j=1;j<=n;j++) p[j]=j;
            int r=0;
            do{
                r++;
                if(!dp[i-1][r]) continue;
                dp[i][r]=1;
                string tmp;
                for(int j=1;j<=n;j++)
                {
                    b[j]=a[i][p[j]];
                    tmp+='0'+b[j];
                }
                dp[i][val[tmp]]=1;
            }while(next_permutation(p+1,p+1+n));
            string tmp;
            for(int j=1;j<=n;j++) tmp+='0'+a[i][j];
            dp[i][val[tmp]]=1;
            //for(int j=0;j<N;j++) rr+=dp[i][j];
            //cout<<i<<' '<<rr<<endl;
        }
        for(int i=0;i<N;i++)ans+=dp[m][i];
        cout<<ans;
    }
    else
    {
        int c[180]={0};
        dfs(1,c);
        cout<<ccc.size();
        // for(auto &[x,y]:ccc)
        // {
        //     cout<<x<<" "<<y<<endl;
        // }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5464kb

input:

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

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

2 1
2 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: -100
Time Limit Exceeded

input:

1 180
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

output:


result: