답안 #448271

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

using namespace std;
int frec[700005];
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[700005];
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=700000;
    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 8 ms 1488 KB Output is correct
2 Correct 99 ms 1604 KB Output is correct
3 Correct 58 ms 1488 KB Output is correct
4 Correct 471 ms 1704 KB Output is correct
5 Correct 1207 ms 1608 KB Output is correct
6 Correct 394 ms 1488 KB Output is correct
7 Correct 551 ms 1616 KB Output is correct
8 Correct 256 ms 1488 KB Output is correct
9 Correct 776 ms 1596 KB Output is correct
10 Correct 822 ms 1488 KB Output is correct
11 Correct 625 ms 1488 KB Output is correct
12 Correct 1173 ms 1488 KB Output is correct
13 Correct 291 ms 1488 KB Output is correct
14 Correct 1389 ms 1608 KB Output is correct
15 Correct 1594 ms 1604 KB Output is correct
16 Correct 1510 ms 1616 KB Output is correct
17 Correct 947 ms 1488 KB Output is correct
18 Execution timed out 2061 ms 1592 KB Time limit exceeded
19 Execution timed out 2063 ms 1608 KB Time limit exceeded
20 Correct 1271 ms 1544 KB Output is correct