【LGR-054】洛谷10月場所II

【LGR-054】洛谷10月場所II
luogu
Codeforces Round#517を消すことに成功した結果、私(mbox{T 4})はまだ書いていません.(\mbox{GG}\) .
エクスプローラ
(mbox{popcount})が(0)の乗上(mbox{popcount})が(1)のものが答えです.
2つの数が異なるか、後のバイナリビット(1)の数のパリティは変わらないからです.
計算(mbox{popcount})については、ルート番号に前処理し、(O(1))計算すればよい.

#include
#include
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
#define ll long long
int n,cnt[65536],sz[2];ll a,b,c,d,x;
int main(){
    n=gi();a=gi();b=gi();c=gi();d=gi();x=gi();
    for (int i=0;i<65536;++i) cnt[i]=cnt[i>>1]^(i&1);
    for (int i=1;i<=n;++i){
        x=(a*x%d*x%d+b*x%d+c)%d;
        ++sz[cnt[x&65535]^cnt[x>>16]];
    }
    printf("%lld
",1ll*sz[0]*sz[1]);
    return 0;
}

マスター
公差を直接列挙し、(n))をスキャンすればよい.

#include
#include
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
const int N = 20005;
const int mod = 998244353;
void inc(int &x,int y){x+=y;x>=mod?x-=mod:x;}
int n,a[N],f[N],s[N],ans;
int main(){
    n=gi();ans=n;
    for (int i=1;i<=n;++i) a[i]=gi();
    for (int i=-20000;i<=20000;++i){
        for (int j=1;j<=n;++j){
            if (a[j]-i>=0&&a[j]-i<=20000) f[j]=s[a[j]-i]+1;
            else f[j]=1;
            inc(s[a[j]],f[j]);inc(ans,f[j]);
        }
        inc(ans,mod-n);
        for (int j=1;j<=n;++j) s[a[j]]=0;
    }
    printf("%d
",ans);return 0;
}

プレゼント
制限条件は、1つの数が別の数のサブセットである場合、2つの数が同じ箱に入れられないことです.
関係に対して(DAG)を作成し、各数は自分のすべてのサブセットに結合し、トポロジー関係を持つ2つの数を一緒に置くことはできません.答えは(DAG)最長チェーン長です.
シナリオを構築するには、ソースポイントが各ポイント(i)に飛び出す最長ルート(f_i)を作成し、(i)は(f_i)と番号付けされた箱に入れればよい.
暴力建辺(3^k)、注意(n=2^k)すなわち(a_i)を遍歴([0,2^k))した場合、この(DAG)を建てるには(O(k 2^k))の辺さえあればいいだけです.不満なら、この(2^k)の点をすべて建てて、存在しない点権値を(0)にして、上記のようにすればいいのです.

#include
#include
#include
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
const int N = 2e6+5;
int n,k,S,vis[N],f[N];vectorans[21];
int main(){
    n=gi();k=gi();S=(1<

ポケットの中の紙飛行機
各数(x)が何種類の数列で生成されるかを計算することを考慮します.さらに、生成された(x)の個数を特定することはできないので、計算(x)がどの数列で生成されないかを考える.
数列の各数対(P)を型抜きし、各([0,P))に(lfloorfrac RPrfloor)または(lfloorfrac RPrfloor+1)の異なる選択が可能になります.
(x=0)の場合は、数列に存在しない(0)を満たすだけです.
(xeq 0)の場合、各(ain[1,P))に対して、一意で互いに異なる(bin[1,P))があり、(atimes b=xmod p)となる.これは、1つの(xeq 0)に対して、交差のない((a,b))がいくつか存在し、同じペアのうちの2つの数が同時に現れないことを要求する.
これの案数はどう計算しますか?あなたは(nle 500)を発見しました.関数を生成しますか?
そんなに引き下がらないようなやり方を言う.(f_{i,j})が前(i)対数で(j)個の位置を埋めたことを示すシナリオ数を考えると,遷移は明らかに現在の対数を何個列挙するとともに,位置が任意に選択できるため1つの組合せ数を乗じなければならない.これを書くと、指数生成関数の畳み込みの形式である(C_i=sum_{j=0}^ibinom ijA_jB_{i,j})であることがわかります.
したがって、各(x)の大概(O(P))の数対に対して、各数対は1つの指数生成関数で表すことができ、この(O(P))個の生成関数を暴力的に巻き込むと、1つの(O(n^2 P^2))を得ることができる.
そして、各([0,P))は(lfloorfrac RPrfloor)または(lfloorfrac RPrfloor+1)種のみ異なる選法であるため、本質的に異なる数対は(3)種のみである.各数対の生成関数を考えてみる.令(B=lfloorfrac RPrfloor)
数対のうち2つの数はいずれも(B)種のみであり,無制限に2つの数を減算して同時に現れるスキームを考える:(A(x)=e^{Bx}e^{Bx}-(e^{Bx}-1)e^{Bx}-1)=2 e^{Bx}-1).このうち(e^{Bx})は実際には((e^x)^B)である.
同じ理屈で(B(x)=e^{Bx}+e^{(B+1)x}-1,C(x)=2 e^{(B+1)x}-1)がある.
ある(x)の3つの数対の個数がそれぞれ(u,v,w)であると仮定すると、(A^u(x)times B^v(x)times C^w(x)times e^{Bx})を計算するだけでよい.
なぜもう一つ(e^{Bx})があるのですか?数列の中には(0)もありますからね.この点に気づいたか?
したがって、まず(A(x)、B(x)、C(x))の(P)乗を前処理し、前処理の複雑さを(O(n^P))にすることができ、その後、各(x)について(O(n^2))でボリュームを計算することができ、総複雑度は(O(n^2 P))であり、(80)点の良い成績を得ることができる.

#include
#include
#include
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
const int mod = 1000000007;
inline void inc(int &x,int y){x+=y;x>=mod?x-=mod:x;}
inline void dec(int &x,int y){x-=y;x<0?x+=mod:x;}
int fastpow(int a,int b){
    int res=1;
    while (b) {if (b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}
    return res;
}
int n,P,R,B,S,inv[5005],C[505][505],ans;
struct poly{
    int a[505];
    poly(){memset(a,0,sizeof(a));}
    poly operator * (poly b){
        poly c;
        for (int i=0;i<=n;++i)
            for (int j=0;j<=i;++j)
                c.a[i]=(c.a[i]+1ll*a[j]*b.a[i-j]%mod*C[i][j])%mod;
        return c;
    }
}dp[3][5005],zero;
int main(){
    n=gi();P=gi();R=gi();B=R/P;
    inv[1]=1;
    for (int i=2;i
0),j)+fastpow(B+(i>1),j))%mod;
        for (int j=2;j<=P;++j) dp[i][j]=dp[i][j-1]*dp[i][1];
    }
    for (int i=0;i<=n;++i) zero.a[i]=fastpow(B,i);
    S=fastpow(R,n);inc(ans,S);dec(ans,fastpow(R-B,n));
    for (int i=1;i

满分做法比较玄学。

首先，要求\(A(x)\)的若干次幂其实只要预处理到根号就行了，即预处理\(A(x),A^2(x),A^3(x)...\)以及\(A^{\sqrt p}(x),A^{2\sqrt p}(x),A^{3\sqrt p}(x)...\)这样预处理的复杂度可以降到\(O(n^2\sqrt P)\)，且对于一个\(x\)仍可以做到\(O(n^2)\)计算。

然后后本部分仍是复杂度瓶颈？发现对于每个\(x\)答案只与三种数对的个数\(u,v,w\)有关，所以加个记忆化......就能过了？

司说本质不同的数对数量是\(O(\sqrt P)\)的，那......就是吧。

#include
#include
#include
#include

転載先:https://www.cnblogs.com/zhoushuyu/p/9830115.html