多校冲刺 noip 10.30
好像我在学校里已经待了30天了吧
几乎是仅次于暑假集训的时间，不过丝毫不慌
因为，咱的成绩在一点点的上升，做题越来越有思路
也不知道是题简单了，还是我的能力提升了，嘿嘿嘿
但是今天考场上又挂分了，处理方式就是多检查，要考虑全所有情况
考场上不能飘起来，要不然所有的分就容易挂掉
比如说今天，我牛逼哄哄的认为我已经\(310pts\)了，然后开玩了，实际上是最后一题不会
注意温故而知新，不然导致丢掉一些重要的东西
T1 特殊字符串
这个我考场上一眼就有\(\mathcal{O(n^2)}\)的\(dp\)
不过优化的话，我还是想了好久好久
我比别人多了个\(log\)树状数组，不过常数确实小，别人慢不了多少
不说了，这个题过于简单了
AC_code
》
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=1e5+5;
int n,m;
char s[N],t[10];
ll pd[30][30],ans;
vector<ll> vec[30];
int len[30],pos[N][30];
void ins(int id,int x,ll v){
for(int i=x;i<=len[id];i+=(i&-i))vec[id][i]=max(vec[id][i],v);
}
ll query(int id,int x){
ll ret=0;
for(int i=x;i;i-=(i&-i))ret=max(ret,vec[id][i]);
return ret;
}
signed main(){
freopen("shiki.in","r",stdin);
freopen("shiki.out","w",stdout);
scanf("%d",&n);
scanf("%s",s+1);
scanf("%d",&m);getchar();
fo(i,0,25)vec[i].push_back(0);
for(int i=1,x;i<=m;i++){
scanf(" %c %c %d",&t[1],&t[2],&x);
pd[t[1]-'a'][t[2]-'a']+=x;
}
fo(i,1,n){
len[s[i]-'a']++;
vec[s[i]-'a'].push_back(0);
fo(j,0,25)pos[i][j]=len[j]+1;
}
fo(i,1,n){
ll res=query(s[i]-'a',pos[i][s[i]-'a']-1);
ans=max(ans,res);
fo(j,0,25)ins(j,pos[i][j],res+pd[s[i]-'a'][j]);
}
printf("%lld",ans);
return 0;
}
T2 宝可梦
这个？？好像就是直接找到你要走的那个环就好了
但是注意方向不同路线也不同，所以找环的时候要算上方向
直接循环一遍就好了，最后询问的时候直接减就是答案了
AC_code
》
#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=1e5+5;
const int M=5e5+5;
int n,m,q;
char s[N];
int mx[4]={-1,0,1,0};
int my[4]={0,-1,0,1};//0 上 1 左 2 下 3 右
vector<int> jz[N],id[4][N];
int step,cnt,pos[M*4];
bool jud(int x,int y){return x<=n&&x>0&&y<=m&&y>0&&jz[x][y];}
signed main(){
freopen("pokemon.in","r",stdin);
freopen("pokemon.out","w",stdout);
scanf("%d%d",&n,&m);int nx=0,ny=0,fx;
fo(i,1,n){
jz[i].reserve(m+10);jz[i].resize(m+5);
fo(j,0,3)id[j][i].reserve(m+10),id[j][i].resize(m+5);
scanf("%s",s+1);
fo(j,1,m){
fo(k,0,3)id[k][i][j]=++cnt;
if(s[j]=='.')jz[i][j]=1;
}
}
fo(i,1,n){
fo(j,1,m){
if(!jz[i][j])continue;
fo(k,0,3){
if(jud(i+mx[k],j+my[k])){
nx=i+mx[k];
ny=j+my[k];
fx=k;
break;
}
}
if(nx)break;
}
if(nx)break;
}
while(!pos[id[fx][nx][ny]]){
step++;pos[id[fx][nx][ny]]=step;
for(int i=fx-1<0?fx+3:fx-1,j=1;j<=4;i=i+1>3?i-3:i+1,j++){
if(jud(nx+mx[i],ny+my[i])){
nx+=mx[i];ny+=my[i];
fx=i;break;
}
}
}
scanf("%d",&q);
while(q--){
int sx,sy,tx,ty,xt;char fxt;
scanf("%d%d%d%d %c",&sx,&sy,&tx,&ty,&fxt);
if(fxt=='U')xt=0;
else if(fxt=='L')xt=1;
else if(fxt=='D')xt=2;
else xt=3;
int st=pos[id[xt][sx+mx[xt]][sy+my[xt]]]-1==0?step:pos[id[xt][sx+mx[xt]][sy+my[xt]]]-1,ed=0x3f3f3f3f;
fo(i,0,3){
if(pos[id[i][tx][ty]])
ed=min(pos[id[i][tx][ty]]<st?pos[id[i][tx][ty]]+step:pos[id[i][tx][ty]],ed);
}
printf("%d\n",ed-st);
}
return 0;
}
T3 矩阵
这个我竟然因为\(if\)没有括号，并且没有跟\(1\)取\(max\)导致爆零了！！！
气死我了，所以这个题的最大长度只有\(log\)，直接搜就行了
\(dfs\)的话就得记忆化，我用的拓扑
AC_code
》
#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=40005;
int n,m,ans;
int mx[4]={-1,0,1,0};
int my[4]={0,-1,0,1};//0 上 1 左 2 下 3 右
bool jud(int x,int y){return x<=n&&x>0&&y<=m&&y>0;}
vector<int> jz[N],ji[N],id[N];
int cnt;
queue<int> q[N];
pair<int,int> wo[N];
int dep[N];
bool vis[N];
signed main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d%d",&n,&m);
fo(i,1,n){
jz[i].reserve(m+10);
jz[i].resize(m+5);
id[i].reserve(m+10);
id[i].resize(m+5);
fo(j,1,m){
scanf("%d",&jz[i][j]);
id[i][j]=++cnt;
wo[cnt]=make_pair(i,j);
}
}
bool flag=false;
fo(i,1,n){
fo(j,1,m){
fo(k,0,3)
if(jud(i+mx[k],j+my[k]))
if(jz[i][j]==jz[i+mx[k]][j+my[k]])
{flag=true;break;}
if(flag)break;
}
if(flag)break;
}
if(flag){printf("-1");return 0;}
fo(i,1,n){
fo(j,1,m){
fo(k,0,3){
if(!jud(i+mx[k],j+my[k]))continue;
if(jz[i+mx[k]][j+my[k]]<jz[i][j])continue;
if(jz[i+mx[k]][j+my[k]]%jz[i][j]!=0)continue;
int now=jz[i+mx[k]][j+my[k]]/jz[i][j];
bool flag=true;
fo(l,0,3){
if(l==k||!jud(i+mx[l],j+my[l]))continue;
if(jz[i+mx[l]][j+my[l]]>jz[i][j])continue;
if(jz[i][j]%jz[i+mx[l]][j+my[l]]!=0)continue;
if(jz[i][j]/jz[i+mx[l]][j+my[l]]==now)flag=false;
}
//cout<<i<<" "<<j<<" "<<k<<" "<<now<<endl;
if(flag)q[now].push(id[i][j]),ji[now].push_back(id[i][j]);
}
fo(k,0,3){
if(!jud(i+mx[k],j+my[k]))continue;
if(jz[i+mx[k]][j+my[k]]>jz[i][j])continue;
if(jz[i][j]%jz[i+mx[k]][j+my[k]]!=0)continue;
int now=jz[i][j]/jz[i+mx[k]][j+my[k]];
q[now].push(id[i][j]),ji[now].push_back(id[i][j]);
}
}
}
fo(i,1,40000){
if(q[i].empty())continue;
for(int j:ji[i])vis[j]=false,dep[j]=1;
while(!q[i].empty()){
int idd=q[i].front();q[i].pop();
ans=max(ans,dep[idd]);
if(ans>=16)break;
int x=wo[idd].first,y=wo[idd].second;
//cout<<i<<" "<<x<<" "<<y<<" "<<dep[idd]<<endl;
fo(j,0,3){
int tx=x+mx[j],ty=y+my[j];
if(!jud(tx,ty))continue;
if(jz[x][y]*i!=jz[tx][ty])continue;
bool flag=true;
q[i].push(id[tx][ty]),dep[id[tx][ty]]=dep[idd]+1;
}
}
if(ans>=16)break;
}
ans=max(ans,1);
printf("%d",ans);
return 0;
}
T4 乘法
这个真的好难，我来写一篇正经的题解！！！
我们发现直接求是不可能的，但是这个题有一个很好的性质，可以直接用\(unsigned\ long\ long\)自然溢出
但是去掉后缀\(0\)这个问题，可以直接把所有的\(2\)都提出来，最后\(\%4\)再乘回去，注意是个数%4
那么我们分奇偶来考虑。
发现对于偶数的情况直接除以二就可以变成奇数的情况
所以我们开始递归......
对于\(n\)个数来说，有\(\frac{n-1}{2}\)个奇数，有\(\frac{n}{2}\)个偶数
我们先处理出所有奇数的乘积的答案，偶数可以整体除以二变成一个子问题
这样就可以在\(log\)的时间复杂度内由当前的值得到最终的答案
那么接下来考虑如何得到\(n\)个数里面所有奇数乘积的答案
设其为\(f_{\frac{n-1}{2}}\)，那么\(ans=f_{\frac{n-1}{2}}*f_{\frac{\frac{n-1}{2}-1}{2}}*...\)
每一个奇数都可以表示为\(2*n+1\)的形式，所以：
\[f_{\frac{n-1}{2}}=\prod\limits_{i=0}^{\frac{n-1}{2}}(2*i+1) \]但是你发现这个几乎没有什么优化的余地了，那么我们考虑拆开括号
拆开之后就是给你一堆\(2*i\)和\(1\)的二元组，每一组选一个，最终求的就是所有方案的乘积的加和
那么我们设\(g_{i,j}\)表示，在\(i\)个二元组中选择\(j\)个\(2*i\)，剩下的全部选择\(1\)的所有方案的答案的加和
发现我们最多选择\(63\)个\(2*i\)这样的，因为再多的话就是0了，因为模数是\(2^{64}\)
这里的\(g\)仍然不是很好，我们把所有的\(2\)都提出来：
\[f_{n}=\sum\limits_{i=0}^{min(n,63)}g_{n,i}*2^i \]那么接下来就是如何求\(g\)数组了
我们可以先想一想这个\(g\)数组的递推式，好像是......：
\[g_{n,m}=(n-1)*g_{n-1,m-1}+g_{n-1,m} \]话说你不觉得看着这个式子很眼熟吗？？
第一类斯特林数！！！
但是不是完全一样，它的\((n-1)\)乘错地方了
要不是仔细看看，还真看不出来，我们把含义进行转化，如果我的\((n-1)\)乘在后面的话
那么我们就可以用第一类斯特林数解决了！！
乘过去试一试：
\[g_{n,m}=g_{n-1,m-1}+(n-1)*g_{n-1,m} \]于是我发现，好像现在的含义就是我把不选在\(m\)个数里的数乘上了，但是乘的时候每一个数都少\(1\)
咋办？？加上\(1\)不就好了？？！！！：
\[g_{n,m}={n+1 \brack n+1-m} \]好了我们成功的将这个数组转化成了斯特林数，这样的话求解办法就有很多了
可以拉格朗日差值，因为斯特林数是一个\(2*m\)次的多项式，但是我并不是很熟练的掌握这个
所以我们用\(dp\)来解决这个问题
因为这个题的\(n-m\)非常的小，所以环的大小大于\(1\)的也就非常少，我们可以对这些环进行\(dp\)
设\(dp_{i,j}\)表示，\(i\)个数分成\(j\)个环的圆排列，每一个环的大小都大于等于\(2\)的方案数
那么斯特林数可以表示为(枚举环大小大于\(1\)的环的个数):
\[{n \brack m}=\sum\limits_{i=0}^{m}{n \choose n-m+i}dp_{n-m+i,i} \]于是我们就需要求出来这个\(dp\)数组
可以很容易的想到转移，这个是一个经典的转移
我们钦定第一个点在某一个环中，我们枚举这个环的大小，从\(i-1\)转移过来
这里必须钦定一个点，不然的话因为环没有顺序会导致算重
转移方程式长成这样：
\[dp_{i,j}=\sum\limits_{k=2}^{i}{i-1 \choose k-1}(k-1)!dp_{i-k,j-1} \]于是这个题到这里我们就全部做完了，接下来整理一下式子
\[dp_{i,j}=\sum\limits_{k=2}^{i}{i-1 \choose k-1}(k-1)!dp_{i-k,j-1} \\ {n \brack m}=\sum\limits_{i=0}^{m}{n \choose n-m+i}dp_{n-m+i,i} \\ g_{n,m}={n+1 \brack n+1-m} \\ f_{n}=\sum\limits_{i=0}^{min(n,63)}g_{n,i}*2^i \]其实在递归的时候可以不用递归实现，直接循环就可以了，最后再把所有的\(2\)乘上去
但是你发现好像式子有是有了，但是这个组合数咋弄啊
注意到模数是个偶数，所以对于所有的偶数都是没有逆元的，咋办？？
对于组合数来说，分母的\(2\)的个数一定少于分子，要不然除不尽啊
所以我们可以先把上下两个数中的\(2\)约掉，这样分母剩下的一定是一个奇数
而奇数的逆元是可以求的，由奇数和\(2^{64}\)互质，由欧拉定理可得
\[a^{\phi(m)}\equiv 1(mod\ m) \]那这样的话，逆元就是\(a^{\phi(m)-1}\)
就这样，结束了，复杂度是递归一个\(log\)，求\(f\)一个\(log\)，求斯特林数两个\(log\)(求组合数还有一个)
\(dp\)数组预处理
所以总复杂度是\(\mathcal{O(log^4n)}\)
AC_code
》
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int ksm(int x,int y){
int ret=1;
while(y){
if(y&1)ret=ret*x;
x=x*x;y>>=1;
}return ret;
}
int T,n,ans;
int dp[155][75];
int inv[155],jc[155];
int c[155][155];
void get_inv(){fo(i,1,150)if(i&1)inv[i]=ksm(i,(1ull<<63)-1);}
void get_jc(){jc[0]=1;fo(i,1,150)jc[i]=jc[i-1]*i;}
int C(int x,int y){
int fm=1,fz=1,sum=0;
fo(i,x-y+1,x){
int now=i;
while(now%2==0)now/=2,sum++;
fz*=now;
}
fo(i,1,y){
int now=i;
while(now%2==0)now/=2,sum--;
fm*=inv[now];
}
return fz*ksm(2,sum)*fm;
}
void get_c(){
c[0][0]=1;
fo(i,1,150){
c[i][0]=1;
fo(j,1,i)c[i][j]=c[i-1][j-1]+c[i-1][j];
}
}
void get_dp(){
dp[0][0]=1;
fo(i,1,150){
fo(j,1,70){
fo(k,2,i){
dp[i][j]=(dp[i][j]+c[i-1][k-1]*jc[k-1]*dp[i-k][j-1]);
}
}
}
}
int stl(int x,int y){
int ret=0;
fo(i,0,min(y,63ull))ret=(ret+C(x,x-y+i)*dp[x-y+i][i]);
return ret;
}
int f(int x){
int ret=0;
fo(i,0,min(63ull,x))ret+=stl(x+1,x+1-i)<<i;
return ret;
}
void print(int x){
char s[20];
int pos=16;
fo(i,1,16){
if(x==0){pos=i-1;break;}
int now=x%16;x/=16;
if(now<10)s[i]=(char)(now+'0');
else s[i]=(char)(now-10+'A');
}
fu(i,pos,1)printf("%c",s[i]);printf("\n");
}
signed main(){
freopen("multiplication.in","r",stdin);
freopen("multiplication.out","w",stdout);
get_jc();get_inv();
get_c();get_dp();
scanf("%llu",&T);
while(T--){
scanf("%llu",&n);
ans=1;int now=n,sum=0;
while(now){
sum+=now>>1;
ans=(ans*f(now-1>>1));
now>>=1;
}
sum%=4;ans=ans*(1ull<<sum);
print(ans);
}
}