Submission #907958

#	Time	Username	Problem	Language	Result	Execution time	Memory
907958		ibm2006	Ljetopica (COI19_ljetopica)	C++17	100 / 100	65 ms	230336 KiB

ljetopica

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,a[1100000],b[1100000],com[5500][5500],tw[5500],dp[1100][1100],ans;
char c;
const ll mod=1000000007;
ll C(ll x,ll y)
{
    if(x<0||y<0||y>x)
        return 0;
        return com[x][y];
}
ll two(ll x)
{
    return tw[x];
}
ll f(ll x,ll y,ll z,ll w=0)
{
   // printf("(%lld,%lld,%lld,%lld)\n",x,y,z,w);
    if(y<0)
        return 0;
    if(x==1&&y==0)
        return (z+two(n-1)-1)%mod;
        if(x==1)
            return 0;
    ll i;
    ll s=0;
    if(b[n-x+2]==0)
    {
        if(a[n-x+1]^w==0)
            return f(x-1,y,z,w);
    else
        return f(x-1,y-1,z,w^1);
    }
    else
    {
        if(a[n-x+1]^w==0)
        {
            if(w==0)
            {s=dp[x-1][y]+C(x-2,y)*((two(n-1)+z-1-two(x-2))%mod)%mod;
            //printf("[%lld,%lld:%lld]\n",x-1,y,dp[x-1][y]);
            }
            else
            {
                s=-C(x-2,y)*((two(n-1)+z-1-two(x-2))%mod)%mod+C(x-2,y)*((two(n-1)-1+z+two(n-1)-1+z+two(x-2)-1)%mod)%mod-dp[x-1][y];
               // printf("{%lld}",s);
            }
            s+=f(x-1,y-1,z+two(x-2),w^1);
            s%=mod;
            s+=mod;
            s%=mod;
            return s;
        }
        /*printf("!");
        if(w==0)
        if(y>=1)
        {
            s=dp[x-1][y-1]+C(x-2,y-1)*(two(n-1)+z-2)%mod;
        }
        s+=f(x-1,y,z+two(x-2),w);
        s%=mod;
        return s;*/
        if(y>=0)
        {if(w==1)
            {s=dp[x-1][y-1]+C(x-2,y-1)*((two(n-1)+z-1-two(x-2))%mod)%mod;
            }
            else
            {
                s=-C(x-2,y-1)*((two(n-1)+z-1-two(x-2))%mod)%mod+C(x-2,y-1)*((two(n-1)-1+z+two(n-1)-1+z+two(x-2)-1)%mod)%mod-dp[x-1][y-1];
                //printf("{%lld,%lld}",s,dp[x-1][y-1]);
            }
        }
            s+=f(x-1,y,z+two(x-2),w);
            s%=mod;
            s+=mod;
            s%=mod;
            return s;
    }
}
ll num(ll x,ll y,ll w=0)
{
    if(y<0)
        return 0;
    if(x==1)
        return z;
    ll i;
    ll s=0;
    if(b[n-x+2]==0)
    {
        if(a[n-x+1]^w==0)
            return num(x-1,y,w);
        else
            return num(x-1,y-1,w^1);
    }
    if(a[n-x+1]^w==0)
    {
        s=C(x-2,y);
        s+=num(x-1,y-1,w^1);
        return s;
    }
    s=C(x-2,y-1);
    s+=num(x-1,y,w);
    return s;
}
int main()
{
    tw[0]=1;
    com[0][0]=1;
    for(i=1;i<=5000;i++)
    {
        for(j=0;j<=i;j++)
        {
            if(j==0)
            {
                com[i][j]=1;
                continue;
            }
            com[i][j]=(com[i-1][j]+com[i-1][j-1])%mod;
        }
    }
    for(i=1;i<=5000;i++)
    {
        tw[i]=tw[i-1]*2%mod;
    }
    scanf("%lld %lld\n",&n,&k);
    for(i=1;i<n;i++)
    {
        scanf("%c",&c);
        if(c=='L')
        {
            a[i]=0;
        }
        else
        {
            a[i]=1;
        }
    }
    dp[1][0]=1;
    for(i=2;i<=n;i++)
    {
        for(j=0;j<i;j++)
        {
            if(a[n-i+1]==0)
            {
                if(j==0)
                {
                    dp[i][j]=(dp[i-1][j]+C(i-2,j)*two(i-2))%mod;
                }
                else
                {dp[i][j]=dp[i-1][j]+C(i-2,j)*two(i-2)%mod+(two(i-2)*3+two(i-1)-1)%mod*C(i-2,j-1)%mod-dp[i-1][j-1];}
                dp[i][j]%=mod;
                dp[i][j]=(dp[i][j]+mod)%mod;
            }
            else
            {
                if(j==0)
                {
                    dp[i][j]=(dp[i-1][j]+C(i-2,j)*two(i-1))%mod;
                }
                else
                dp[i][j]=dp[i-1][j]+C(i-2,j)*two(i-1)%mod+(two(i)-1)*C(i-2,j-1)%mod-dp[i-1][j-1];
                dp[i][j]%=mod;
                dp[i][j]=(dp[i][j]+mod)%mod;
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        scanf("%01lld",&b[i]);
    }
    for(i=n;i>=2;i--)
    {
        b[i]++;
        b[i-1]+=b[i]/2;
        b[i]%=2;
    }
    b[1]=1;
    /*for(i=1;i<=n;i++)
        printf("%lld",b[i]);
    printf("\n");
    */ans-=f(n,k,1);
    //printf("%lld\n",ans);
    /*for(i=2;i<=n;i++)
    {
        b[i]^=1;
    }
    ans-=num(n,k)*(two(n)+two(n-1)-1)%mod-f(n,k,1);*/
    ans-=f(n,k,1,1);
    //printf("%lld\n",ans);
    for(i=1;i<=n;i++)
    {
        scanf("%01lld",&b[i]);
    }
ans+=f(n,k,1);
//printf("%lld\n",ans);
    /*for(i=2;i<=n;i++)
    {
        b[i]^=1;
    }*/
    //ans+=num(n,k)*(two(n)+two(n-1)-1)%mod-f(n,k,1);
    ans+=f(n,k,1,1);
    /*if(k>=1)
    {
        ans=dp[n][k]+dp[n][k-1]+(two(n)-1+two(n-1))*C(n-1,k)%mod-dp[n][k]-dp[n][k-1];
    }
    else
    {
        ans=dp[n][k]+two(n)-1+two(n-1)-dp[n][k];
    }*/
    ans%=mod;
    ans+=mod;
    ans%=mod;
    printf("%lld",ans%mod);
}

Compilation message (stderr)

ljetopica.cpp: In function 'll C(ll, ll)':
ljetopica.cpp:9:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    9 |     if(x<0||y<0||y>x)
      |     ^~
ljetopica.cpp:11:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   11 |         return com[x][y];
      |         ^~~~~~
ljetopica.cpp: In function 'll f(ll, ll, ll, ll)':
ljetopica.cpp:22:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   22 |     if(x==1&&y==0)
      |     ^~
ljetopica.cpp:24:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   24 |         if(x==1)
      |         ^~
ljetopica.cpp:30:22: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   30 |         if(a[n-x+1]^w==0)
      |                     ~^~~
ljetopica.cpp:37:22: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   37 |         if(a[n-x+1]^w==0)
      |                     ~^~~
ljetopica.cpp:26:8: warning: unused variable 'i' [-Wunused-variable]
   26 |     ll i;
      |        ^
ljetopica.cpp: In function 'll num(ll, ll, ll)':
ljetopica.cpp:90:22: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   90 |         if(a[n-x+1]^w==0)
      |                     ~^~~
ljetopica.cpp:95:18: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   95 |     if(a[n-x+1]^w==0)
      |                 ~^~~
ljetopica.cpp:86:8: warning: unused variable 'i' [-Wunused-variable]
   86 |     ll i;
      |        ^
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     scanf("%lld %lld\n",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
ljetopica.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         scanf("%c",&c);
      |         ~~~~~^~~~~~~~~
ljetopica.cpp:169:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         scanf("%01lld",&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
ljetopica.cpp:192:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |         scanf("%01lld",&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 17 / 17
• Subtask 4: 61 / 61