hdu 6129 Just do it

12117 ワード

リンク
http://acm.hdu.edu.cn/showproblem.php?pid=6129
問題を解く
最初の数が後に与える影響を考慮して、a a a a^k akでa a a自身の異異種またはk k k k回a、b、c a、b、b、b、b、b、c、a、b、a b、a b、b b、b、a a a a a 3 b、a 3 b 2 c、a 2 b、a^2 b、a 3 b 3 b 3 b^2 c、a 2 a 2 a、a 2 a 3 b、a 2 a 3 b、a 3 a 3 a 3 b、a 3 a 3 a 3 a 3 a 3 a 3 b、a 3 a 3 a 3 a 3 a 3 a 3 b、a 3 a 3 a 3 b、a 3 a 3 a 3 a 3 b、a 3 a 3 a 3 a 3 a 3 a、a 3 a 3 a 3 b、a 3 a 3 a、a^4 b、a^{10}b^3、c a、a 4 b、a 10 b 3、c次にa aの異数のマトリクスを1 0 1 1 1 1 1 2 3 1 3 6 1 4 10と書きます.もっと幅を広く書いてもいいです.1 1 1 1 1 1 1 1 1 1 2 4 1 3 3 6 10.
私自身もここまでしましたが、規則がよく分かりません.横に見て縦に見ます.下手をしても規則が分かりません.
インターネットで問題を調べたら、何ですか?斜めに見られますか斜めに見ると楊輝三角ですか?
私の負けです
斜めに見ると確かに楊輝三角です.
与えられた行と列が0から始まると、i番目のi行のj番目のj個数はC i+j_C__である.{i+j}^j Ci+jjでは、最後の行のi番目の個数がC m−1 i i C_である.{m-1_i}^i Cm−1 i
私は数字のパリティだけを確認します.これは後ろに貢献しているかどうかを知ることができます.これは直接階乗内の2つの数を数えることができます.この係数が奇数なら、この場所を1に設定します.さもなければ0に設定します.
その後の数の係数は最初の係数の並進です.最後の数値を算出します.
その後はできません.多項式の計算に似ていると思います.
問題解を見たら、暴力ばかりですか?
ほとんどの係数が0に等しく、少数が1に等しいからです.
この問題はあまりにも神すぎます
コード
#include 
#define maxn 200010
#define cl(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
ll read(ll x=0)
{
    ll c, f(1);
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-48;
    return f*x;
}
ll n, a[maxn], m;
ll count2(ll x)
{
    ll ans(0);
    while(x)
    {
        ans+=x>>1;
        x>>=1;
    }
    return ans;
}
ll calc(ll n, ll m)
{
    ll ans=count2(n)-count2(m)-count2(n-m);
    return ans;
}
ll ans[maxn], c[maxn];
int main()
{
    ll i, j, T=read();
    while(T--)
    {
        n=read(), m=read();
        for(i=0;i<n;i++)a[i]=read();
        cl(ans);
        for(i=0;i<n;i++)
        {
            auto t=calc(m+i-1,i);
            if(t==0)
            {
                for(j=i;j<n;j++)
                {
                    ans[j]^=a[j-i];
                }
            }
        }
        for(i=0;i<n;i++)
        {
            printf("%lld",ans[i]);
            if(i<n-1)putchar(32);
        }
        putchar(10);
    }
    return 0;
}