[NOIP2017 A팀 합숙훈련 향상 10.22] 우정.

Description


Flowey는 우정의 알갱이를 통해 LOVE를 전파할 수 있는 작은 꽃이다. 우정의 알갱이는 두 가지로 나뉘는데, 둥근 알갱이와 구겨진 알갱이가 순서대로 배열되어 길이가 2m의 서열을 이루고 있다. 우정의 알갱이에 대한 서열은 1<=i

Solution


이 문제는 60점 만점에 f[i][j][k]를 설정하여 i번, 짝수의 둥근 알갱이와 주름 알갱이의 개수를 맞추고 옮긴다. 앞의 짝만 옮길 수 있다는 것을 주의해야 한다.우리는 가장 번거로운 것이 바로 위의 제한이라는 것을 발견했다.수량이 2n을 초과하지 않도록 요구하려면 앞에서 n개의 짝수(원립+주름알=n)를 강제로 놓고 뒤에 맞지 않는 홀수가 앞에 있는 n과 일치하기만 하면 합법적이다.우리는 짝수로 합쳐졌기 때문에 짝수의 개수는 반드시 줄어들지 않을 것이다. (짝수로 들어오면 짝수가 일치하지 않고 성공 짝수의 총수는 n이다) 그러면 둥근 입자인지 주름 입자인지의 문제이다. f[i][j]를 설정하면 i번째 짝수 둥근 입자가 j개이고 짝수 주름이 n-j개이기 때문에 60점처럼 강제로 이동할 수 있다.그러나 우리는 무게를 계산할 수 있고, 무게를 계산할 수 있는 경우가 많다는 것을 발견했다.그러나 우리는 j=0일 때 무거운 편이 아니라는 것을 발견했다. 왜냐하면 이때의 서열은 유일하게 확정된 것이기 때문에 우리는 0에 도달했는지 여부를 표시하는 1차원을 더 기록해야 한다.그러나 우리는 첫 번째 홀수는 앞의 짝수에 일치하지 않는다는 것을 발견할 수 있다. 그래서 이 홀수와 다른 짝수의 색깔은 자유롭다. 마지막 답은 *4

Code

#include
#include
#include
#include
#include
#define fo(i,a,b) for(i=a;i<=b;i++)
#define min(a,b) (a
using namespace std;
typedef long long ll;
const int maxn=3007;
ll i,j,k,l,t,n,m,ans,mo,u,v;
ll f[maxn][maxn][2];
int main(){
    freopen("friend.in","r",stdin);
    freopen("friend.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&mo);n--,m--;
    fo(i,1,n)f[0][i][0]=1;f[0][0][1]=1;
    fo(i,0,m-1){
        fo(j,0,n){
            f[i+1][j][0]=(f[i+1][j][0]+2*f[i][j][0])%mo;
            f[i+1][j][1]=(f[i+1][j][1]+2*f[i][j][1])%mo;
            f[i+1][j+1][0]=(f[i+1][j+1][0]+f[i][j][0])%mo;
            f[i+1][j+1][1]=(f[i+1][j+1][1]+f[i][j][1])%mo;
            if(j){
                if(j==1)f[i+1][j-1][1]=(f[i+1][j-1][1]+f[i][j][1]+
                f[i][j][0])%mo;
                else f[i+1][j-1][1]=(f[i+1][j-1][1]+f[i][j][1])%mo
                ,f[i+1][j-1][0]=(f[i+1][j-1][0]+f[i][j][0])%mo;
            }
        }
    }
    fo(i,0,n)ans=(ans+f[m][i][1])%mo;
    printf("%lld
"
,ans*4%mo); }

좋은 웹페이지 즐겨찾기