답안 #448272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
448272 2021-07-29T13:07:17 Z stefantaga 힘 센 거북 (IZhO11_turtle) C++14
90 / 100
2000 ms 1488 KB
#include <bits/stdc++.h>

using namespace std;
int frec[600005];
int fr[1005][1005],din[1005][1005][21];
long long k,t,z,n,m;
struct wow
{
    int x,y;
} v[105];
vector <int> prime;
bool c[600005];
long long lim;
long long ridput (long long a,long long b)
{
    if (b==0)
    {
        return 1;
    }
    long long rez=ridput(a,b/2);
    if (b%2==0)
    {
        return (rez*rez)%z;
    }
    return ((rez*rez)%z*a)%z;
}
void adauga(int n,int val)
{
    int j;
    for (j=0; j<(int)prime.size(); j++)
    {
        long long p=prime[j];
        while (p<=n)
        {
            long long sal=(n/p);
            frec[j]=frec[j]+1LL*sal*val;
            p=p*prime[j];
        }
    }
}
long long combinari(int k,int n)
{
    int j;
    for (j=0; j<(int)prime.size(); j++)
    {
        frec[j]=0;
    }
    adauga(n,1);
    adauga(k,-1);
    adauga(n-k,-1);
    long long p=1;
    for (j=0; j<(int)prime.size(); j++)
    {
        p=(p*ridput(prime[j],frec[j]))%z;
    }
    return p;
}
bool dif (int x,int y,int x2,int y2)
{
    if (x!=x2||y!=y2)
    {
        return 1;
    }
    return 0;
}
bool nimic(int x,int y,int x2,int y2)
{
    for (int i=1; i<=k; i++)
    {
        if (dif(v[i].x,v[i].y,x,y)==1&&dif(v[i].x,v[i].y,x2,y2)==1)
        {
            if (x<=v[i].x&&v[i].x<=x2&&y<=v[i].y&&v[i].y<=y2)
            {
                return 0;
            }
        }
    }
    return 1;
}
map <pair <int,int> ,long long > mr;
long long nimicpr[105][105];
long long nr(int st,int dr)
{
    int x=v[st].x;
    int y=v[st].y;
    int x2=v[dr].x;
    int y2=v[dr].y;
    if (x>x2||y>y2)
    {
        swap(st,dr);
        swap(x,x2);
        swap(y,y2);
    }
    long long inc=combinari(x2-x,x2-x+y2-y);
    if (nimic(x,y,x2,y2)==1)
    {
        return combinari(x2-x,x2-x+y2-y);
    }
    if (mr.find({st,dr})!=mr.end())
    {
            return mr[{st,dr}];
    }
    for (int i=1;i<=k;i++)
    {
        if (dif(v[i].x,v[i].y,x,y)==1&&dif(v[i].x,v[i].y,x2,y2)==1)
        {
            if (x<=v[i].x&&v[i].x<=x2&&y<=v[i].y&&v[i].y<=y2)
            {
                inc=(inc-(1LL*nr(st,i)*combinari(x2-v[i].x,x2-v[i].x+y2-v[i].y))%z+z)%z;
            }
        }
    }
    mr[{st,dr}]=mr[{dr,st}]=inc;
    return inc;
}
long long brut()
{
    int i,j;
    for (i=1; i<=k; i++)
    {
        fr[v[i].x][v[i].y]=1;
    }
    din[1][1][0]=1;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            if (i!=1||j!=1)
            {
                for (int r=fr[i][j]; r<=k; r++)
                {
                    din[i][j][r]=(din[i][j][r]+din[i-1][j][r-fr[i][j]]+din[i][j-1][r-fr[i][j]])%z;
                }
            }
        }
    }
    long long sum=0;
    for (int r=0; r<=t; r++)
    {
        sum=(sum+din[n][m][r])%z;
    }
    return sum;
}
bool compare(int a,int b)
{
    return v[a].x<v[b].x||(v[a].x==v[b].x&&v[a].y<v[b].y);
}
long long i,j,dist[105][105];
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
#ifdef HOME
    ifstream cin("turtle.in");
    ofstream cout("turtle.out");
#endif // HOME
    cin>>n>>m>>k>>t>>z;
    n++;
    m++;
    lim=600000;
    c[0]=c[1]=1;
    for (i=2; i<=lim; i++)
    {
        if (c[i]==0)
        {
            prime.push_back(i);
            for (j=i*i; j<=lim; j+=i)
            {
                c[j]=1;
            }
        }
    }
    for (i=1; i<=k; i++)
    {
        cin>>v[i].x>>v[i].y;
        v[i].x++;
        v[i].y++;
    }
    v[0].x=1;
    v[0].y=1;
    v[k+1].x=n;
    v[k+1].y=m;
    lim=(1<<k);
    for (i=0;i<=k+1;i++)
    {
        for (j=0;j<=k+1;j++)
        {
            if (i!=j)
            {
                dist[i][j]=dist[j][i]=nr(i,j);
            }
        }
    }
    long long sum=nr(0,k+1);
    for (int i=1;i<lim;i++)
    {
        vector <int> sol;
        for (int j=0;j<k;j++)
        {
            if (i&(1<<j))
            {
                sol.push_back(j+1);
            }
        }
        int ok=1;
        sort (sol.begin(),sol.end(),compare);
        for (int j=1;j<sol.size();j++)
        {
            if (v[sol[j-1]].y>v[sol[j]].y)
            {
                ok=0;
                break;
            }
        }
        if (sol.size()>t)
        {
            ok=0;
        }
        if (ok==0)
        {
            continue;
        }
        long long p=dist[0][sol[0]];
        for (int j=1;j<sol.size();j++)
        {
            p=(p*dist[sol[j-1]][sol[j]])%z;
        }
        int ult=(int)sol.size()-1;
        p=(p*dist[sol[ult]][k+1])%z;
        sum=(sum+p)%z;
    }
    //cout<<brut()<<'\n';
    cout<<sum;
    return 0;
}

Compilation message

turtle.cpp: In function 'int main()':
turtle.cpp:207:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |         for (int j=1;j<sol.size();j++)
      |                      ~^~~~~~~~~~~
turtle.cpp:215:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  215 |         if (sol.size()>t)
      |             ~~~~~~~~~~^~
turtle.cpp:224:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |         for (int j=1;j<sol.size();j++)
      |                      ~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1360 KB Output is correct
2 Correct 76 ms 1360 KB Output is correct
3 Correct 51 ms 1452 KB Output is correct
4 Correct 391 ms 1360 KB Output is correct
5 Correct 1113 ms 1464 KB Output is correct
6 Correct 349 ms 1360 KB Output is correct
7 Correct 463 ms 1452 KB Output is correct
8 Correct 221 ms 1360 KB Output is correct
9 Correct 721 ms 1432 KB Output is correct
10 Correct 740 ms 1360 KB Output is correct
11 Correct 549 ms 1464 KB Output is correct
12 Correct 1052 ms 1436 KB Output is correct
13 Correct 262 ms 1488 KB Output is correct
14 Correct 1210 ms 1448 KB Output is correct
15 Correct 1461 ms 1484 KB Output is correct
16 Correct 1369 ms 1464 KB Output is correct
17 Correct 859 ms 1360 KB Output is correct
18 Execution timed out 2082 ms 1440 KB Time limit exceeded
19 Execution timed out 2087 ms 1360 KB Time limit exceeded
20 Correct 1217 ms 1444 KB Output is correct