您现在的位置是：主页 > news > flash美食网站论文/排名优化公司

flash美食网站论文/排名优化公司

admin2025/6/5 15:28:26【news】

简介flash美食网站论文,排名优化公司,网站模板减肥,企业网站策划stone 首先说明解答正确性存疑（似乎被叉掉了） 存在某堆xi∈[a,b]x_i\in [a,b]xi∈[a,b]，先手必胜。否则设置[a,b][a,b][a,b]区间不可达(谁走到[a,b][a,b][a,b]就输了)构造关于石子个数的SG函数，相当于在必须取某堆石子使其个…

flash美食网站论文,排名优化公司,网站模板减肥,企业网站策划stone 首先说明解答正确性存疑（似乎被叉掉了） 存在某堆xi∈[a,b]x_i\in [a,b]xi∈[a,b]，先手必胜。否则设置[a,b][a,b][a,b]区间不可达(谁走到[a,b][a,b][a,b]就输了)构造关于石子个数的SG函数，相当于在必须取某堆石子使其个…

stone

首先说明解答正确性存疑（似乎被叉掉了）

存在某堆 $xi∈[a,b]x_i\in [a,b]$ ，先手必胜。

否则设置 $[a, b]$ 区间不可达(谁走到 $[a, b]$ 就输了)构造关于石子个数的SG函数，相当于在必须取某堆石子使其个数 $∈[a,b]\in[a,b]$ (必败态)之前的一个SG博弈游戏。

按 $a$ 分类讨论：

$a = 1$ ，从 $b + 1$ 开始，SG按 $0 - b$ 不断循环。
$a > 1$ ，设 $0 - (a - 1)$ 这段 $S G$ 函数为0，将位置 $b$ 的SG函数看作1(实际上不可达)，那么就是从 $b$ 开始的形如 $1, 0, 2, 3 . . .$ 的循环，循环节长度为 $a + b$ ，其中每个数字都出现 $a$ 次。

sequence

$t≤109t\leq 10^9$ 并没有什么用，因为长度为 $i$ 的格子最大只能凑出 $i + m - 1$

$n^2$ DP，注意期望要倒序DP，枚举 $i = 1 - n$ ，强制后 $i - 1$ 位已经选定：

设 $f [i] [j]$ 表示长度限制为 $i$ ，最终(填满)得到的序列第一个格子处为 $j$ 的概率， $g [i] [j]$ 表示其期望答案， $x [i] [j]$ 表示长度限制为 $i$ ，最后在第一个得到 $j$ (其它格为空)的概率， $u [i] [j]$ 表示长度限制为 $i$ ，初始在第一格放上的是 $j$ 的最终(填满)期望答案。

具体转移见代码(感觉还是很巧妙

#include<bits/stdc++.h>
#define gc getchar
#define pb push_back
using namespace std;
const int N=1010,mod=1e9+7;
typedef long long ll;
typedef double db;int n,m,t,p,s[N];
int f[N][N<<1],g[N][N<<1],x[N][N<<1],u[N][N<<1];inline void ad(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline int dc(int x,int y){x-=y;return x<0?x+mod:x;}
inline int inc(int x,int y){x+=y;return x>=mod?x-mod:x;} inline int fp(int x,int y)
{int re=1;for(;y;y>>=1,x=(ll)x*x%mod)if(y&1) re=(ll)re*x%mod;return re; 
}int main(){freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);int i,j,lim,coef;scanf("%d%d%d",&n,&m,&t);p=fp(m,mod-2);for(i=1;i<=n;++i){lim=min(t,i+m-1);for(j=1;j<=lim;++j){coef=(j==t)?1:dc(1,x[i-1][j]);x[i][j]=inc((ll)x[i][j-1]*x[i-1][j-1]%mod,(j<=m)?p:0);f[i][j]=(ll)x[i][j]*coef%mod;if(j==t) g[i][j]=inc(s[i-1],j);else g[i][j]=inc(j,(ll)dc(s[i-1],(ll)x[i-1][j]*u[i-1][j]%mod)*fp(coef,mod-2)%mod);ad(s[i],(ll)f[i][j]*g[i][j]%mod); }for(j=lim;j>0;--j)u[i][j]=inc((ll)x[i-1][j]*u[i][j+1]%mod,(ll)((j==t)?1:dc(1,x[i-1][j]))*g[i][j]%mod);}printf("%d",s[n]);fclose(stdin);fclose(stdout);return 0;
}

tree

以前考过类似的题，但我还是zz了，没有深入分析出来。

莫比乌斯反演后，实际上只有 $μ≠0\mu\neq 0$ 的因子才有贡献，由于 $≤106\leq 10^6$ 的数最多只有 $c = 7$ 个不同的质因子，所以枚举约数个数为 $2^c$ ，并非分解因子的 $n\sqrt n$ 。

对于每个 $i∣gcd⁡i|\gcd$ 都做一遍并查集，求出贡献：
直接加入所有修改不涉及的边，然后枚举第 $1 - q$ 次修改后，处理出所有修改涉及到的这 $q$ 条边的此时的权值，再把这些边加入图，用栈维护可撤回的启发式合并的并查集。

总复杂度 $O(L+(n+q^2)2^c\log n)$ (启发式合并的 $log⁡\log$ )

#include<bits/stdc++.h>
#define gc getchar
#define pb push_back
using namespace std;
const int N=1e5+10,M=1e6+10,MX=102;
typedef long long ll;
typedef double db;int n,m,p[M],num,mu[M];
bool pri[M],ban[M],chg[N];
struct P{int u,v,z;}le[N];
int Q[MX],nt[MX],vl[N];ll cur,ans[MX];
vector<int>L[M];char cp;
template<class T>inline void rd(T &x)
{cp=gc();x=0;int f=0;for(;!isdigit(cp);cp=gc()) if(cp=='-') f=1;for(;isdigit(cp);cp=gc()) x=x*10+(cp^48);if(f) x=-x;
}inline void pre()
{int i,j,res;mu[1]=1;for(i=2;i<M;++i){if(!pri[i]) p[++num]=i,mu[i]=-1;for(j=1;j<=num && (res=i*p[j])<M;++j){pri[res]=true;if(i%p[j]) mu[res]=-mu[i];else break;} }
}namespace bcj{int top,id[N<<1];
struct bb{int f,h,sz;
}stk[N<<1],b[N];inline void init()
{for(int i=1;i<=n;++i) b[i].f=i,b[i].sz=1;}
inline int getfa(int x){return (x==b[x].f)?x:getfa(b[x].f);}
inline void meg(int E)
{int x=getfa(le[E].u),y=getfa(le[E].v);if(x==y) return;cur+=(ll)b[x].sz*b[y].sz;stk[++top]=b[x];id[top]=x;stk[++top]=b[y];id[top]=y;if(b[x].h<b[y].h) swap(x,y);b[x].h=max(b[x].h,b[y].h+1);b[y].f=x;b[x].sz+=b[y].sz;
}}
using namespace bcj;int main(){freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);int i,j,k,x,y,z,nw,mx=0;bool sta;pre();ll lst;rd(n);init();for(i=1;i<n;++i){rd(le[i].u);rd(le[i].v);rd(le[i].z);mx=max(mx,le[i].z);}for(rd(m),i=1;i<=m;++i){rd(Q[i]);rd(nt[i]);chg[Q[i]]=true;mx=max(mx,nt[i]);}for(i=1;i<n;++i){x=le[i].z;sta=chg[i];for(j=1;j*j<=x;++j) if(x%j==0){//if(mu[j]) -> WAif(sta) ban[j]=ban[x/j]=true;else{if(mu[j]) L[j].pb(i);//if(j*j!=x && mu[x/j]) L[x/j].pb(i);//}}}for(i=1;i<=m;++i)for(x=nt[i],j=1;j*j<=x;++j) if(x%j==0)ban[j]=ban[x/j]=true;cur=(ll)n*(n-1)/2;for(i=0;i<=m;++i) ans[i]=cur;for(i=2;i<=mx;++i) if(mu[i]){for(cur=0,j=L[i].size()-1;j>=0;--j) meg(L[i][j]);nw=top;lst=cur;for(j=0;j<=m;++j){if(ban[i]){for(k=j+1;k<=m;++k) vl[Q[k]]=le[Q[k]].z;for(k=1;k<=j;++k) vl[Q[k]]=nt[k];for(k=1;k<=m;++k) if(vl[Q[k]]%i==0) meg(Q[k]);}ans[j]+=mu[i]*cur;for(;top>nw;top--) b[id[top]]=stk[top];cur=lst;}for(;top;--top) b[id[top]]=stk[top];}for(i=0;i<=m;++i) printf("%lld\n",ans[i]);fclose(stdin);fclose(stdout);return 0;
}