济南-1102试题解题报告

By shenben

上午：模拟赛之棋盘上的问题解题报告

T1 cannon	炮
题目大意	在N×M的矩形方格中摆炮使其互不吃到的方案数。
算法一	按每一位置的顺序搜索放与不放

时间复杂度：O(2^(NM))

期望得分：40

算法二	状压DP。因为对于每一列只有三种情况0，1，2个炮，所以可以用三进制对每个状态压缩，然后按每一位置的顺序DP。

时间复杂度：O(N*M*3^M)

期望得分：70

算法三	DP.状态F[i][j][k]表示到第i行每列中的炮1个的有j列，2个的有k列. 转移： 1：此行不添加 2：在0个的列添加1个 3：在1个的列添加1个 4：在两个0个的列分别添加1个 5：在0个的列和1个的列分别添加1个 6：在两个1个的列分别添加1个转移时乘上相应方案数即可。 Ans=sigma(f[n][j][k])(0<=j,k<=m)

时间复杂度：O(N^3)

期望得分：100

T2 rook	車
题目大意	在N×M 的矩形方格中摆最多个数的車使其互不吃到的方案数。
算法一	显然每行每列只能放一个，按题意搜索即可。

时间复杂度：O(N!)

期望得分：20

算法二	显然问题可以转化为求C(n,m)(n>=m，小于则交换) 直接循环计算

时间复杂度：O(N)

期望得分：40

算法三	在算法二的基础上采用高精度计算大整数，处理除法可以采用单精度除法。

时间复杂度：O(N*bignumber()[完整的])

期望得分：70

算法四

求C(n,m)是一个经典问题，有许多优秀的算法。这里笔者提供一种比较简单优美的做法。读者需对筛选质数、快速幂、高精度算法有所掌握。

我们观察筛选质数算法

i=2 to n

if i是质数

J=n/i downto 2

将i*j标记为合数

这个算法可被证明为O(NlogN)的，而且由于除法较少，实测效率可与其他线性的筛法不相上下。我们对这个算法进行改进，原理是质因数分解。我们对于每一个数再记录下最后答案要乘它的tot次方。开始对于tot[1到m]=-1，tot[n-m+1到n]=1。那么我们每次将i*j标记为合数时，顺便把i*j拆分为i和j。而且这样做可以保证最后所有的tot非负（因为答案为整数，除得尽）。然后最后将所有的数的tot次方相乘即可（这步可以用快速幂优化，但实测相差很小），其中只需要高精度乘法。

时间复杂度：O(NlogN*bignumber()[最后50位])

期望得分：100

T3 queen	皇后
题目大意	破棋盘上的n 皇后问题。
算法一	n 皇后问题过于经典，直接套用原问题算法。

时间复杂度：O(N!)

期望得分：20-30

算法二	对原问题算法稍稍改进，每行加一些限制。

时间复杂度：O(N!)

期望得分：70-80

算法三

n 皇后问题还有许多优秀的优化后的算法，如Dancing Links、镜像优化、人工栈等。但这里由于棋盘并不对称所以镜像优化无法使用，人工栈、Dancing Links都太过复杂（其实我现在还不会），所以我们要取性价比最高的优化方法——位运算！

我们可以记录三个状态S1，S2，S3表示当前每行中、两条对角线上哪些位置分别被占。然后位运算牛就牛在我们可以O(1)算出某个数最右边的1在哪里，这样我们再经过简单的转移就可以得到理想的效果。位运算将枚举可行位置优化到了极致！常数小，代码短，而且可以推广，乃居家旅行之必备！

关于位运算的详细分析见matrix67的blog。

http://www.matrix67.com/blog/archives/266

时间复杂度：O(N!)

期望得分：100

另：除了上面的算法外，不排除还有其他更优的解法。

下午：模拟题之task of Euler's totient function解题报告

T1 phi	欧拉函数
算法一	暴力枚举gcd(i,N)=1的i的个数。
	时间复杂度：O(NlogN)	期望得分：20
算法二	在算法一的基础上，求phi用欧拉线性筛法。
	时间复杂度：O(N)	期望得分：20
算法三	令p为N的所有质因子。暴力分解质因子，利用phi(N)=N* 求解。
	时间复杂度：O(sqrt(N))	期望得分：60
算法四	在算法三的基础上,利用rho算法分解质因子。
	时间复杂度：O(N^(1/4)logN)	期望得分：100

T2 arc	反欧拉函数
算法一	暴力枚举N，暴力求出phi(N)验证答案。
	时间复杂度：O(N^1.5)或O(N^2logN)或O(N^(5/4)logN)	期望得分：20-50
算法二	在算法一的基础上，求phi用欧拉线性筛法。
	时间复杂度：O(N)	期望得分：50
算法三	考虑到原数只可能有一个大于10^7的质因子。考虑将phi(N)分解，在10^7范围内从大到小暴力搜索质因子试除(从大到小搜索可使状态树上紧下宽)，并记录对应的N。一个明显的优化就是如果当前数加一为大于10^7的一个质数（用Miller-Rabin素性测试判）就可以停止这一状态的继续搜索了。虽然看起来复杂度很吓人，不过由于满足条件的N较少等等种种原因，实测还是相当快的。
	时间复杂度：O(?)	期望得分：100

calc	欧拉心算(本题不存在，自动忽略就好)
算法一	暴力枚举i,j,求解phi(gcd(i,j))
	时间复杂度：O(N^3.5)	期望得分：20
算法二	在算法一的基础上，求phi用欧拉线性筛法预处理。
	时间复杂度：O(N^2)	期望得分：40
算法三	令g(T)= 。它是两个积性函数的Dirichlet卷积,显然也是一个积性函数，利用欧拉线性筛法求解即可。前面的数值不同的仅sqrt(N)种，对于前面相同的情况，对应g(T)函数连续一段的和，预处理前缀和即可。注意程序常数。
	时空复杂度O(N+Tsqrt(N))/O(N) T为询问总数。	期望得分：100

T3 sum	欧拉函数求和
算法一	暴力枚举i，累加求解。
	时间复杂度：O(N^1.5)	期望得分：20
算法二	在算法一的基础上，求phi用欧拉线性筛法。
	时间复杂度：O(N)	期望得分：60
算法三	由于因此数值不同的仅sqrt(N)种，对于相同的情况，对应函数连续一段的和，预处理前缀和即可，吗？要是这么做就跟算法二没什么区别了。。。。。。前面的枚举是O(sqrt(N))的，算法的瓶颈在于函数求和。那么，如何高效进行函数求和呢？呢？呢？我们设一个函数，那么M(n)实际上满足这么一个性质如果我们先将1至S的M函数值求出（通过欧拉线性筛法预处理），剩下需要用到的M函数的值用类似记忆化搜索的的方法求解即可（当然有不同的sqrt(N)个值，每层搜索枚举是sqrt(N)的）。S的具体取值要平衡预处理和计算的复杂度，还要考虑到程序实际运行的常数。理论上我真不会算。实测对于极限数据貌似是O(N^0.8)。
	时间复杂度：O(N^0.8)	期望得分：100
~~算法四~~	~~O(∩_∩)O哈哈~大打表之术闪亮登场！~~ 我们按10^7为单位，将210^9剖分成200段，我们先假设只算某段里的和。那么问题就转化成了求L-R中phi(i)的和，L,R<=210^9且R-L<=10^7。这个问题可以用Eraosthenes筛法O(nloglogn)解决，因为质因子不会超过sqrt(210^9)，枚举2到sqrt(210^9)，将L-R里每个数扫一遍，最后再找一下对于每一个数剩下的至多一个大质因子。 ~~这样到每段结尾的和也可算出，要先存在表里。（跑200遍无压力么。。。）~~ ~~然后算一遍N所在的那段即可。~~
	~~时间复杂度：O(SlogS)~~ ~~S为剖分的每段长度~~	~~期望得分：100~~

另：除了上面的算法外，不排除还有其他更优的解法。

晚上：noip模拟题day1

取模(mod)

对于一组可能的答案 $c$ ，如果先对一个觉小的 $c_{i}$ 取模，再对一个较大的 $c_{j}$ 取模，那么这个较大的 $c_{j}$ 肯定是没有用的。因此最终的答案序列中的 $c$ 肯定是不增的。那么就枚举选哪些数字，并从大到小取模看看结果是否是 $0$ 就可以了。时间复杂度 $O (2^{n})$ .

等比数列(sequence)

判断是否为等比数列，可以检验对所有1<i<n A[i-1]*A[i+1]=A[i]*A[i] 是否都成立。

直接高精度也是资词的。

比较简单的方法是选择若干质数（保证乘积大于10^200），在模意义下检验。

复杂度O(k*n)。k表示选取的质数个数。

回文串(palindromes)

对原串前缀和后缀作一个01标记pre[i],suf[i]表示1-i和i-n能否能形成回文。记以i为中心的回文半径为r(i)。

这些都可以在O(N)时间内求出。也可以使用Hash+二分等方法O(NlogN)内求出。

我们考虑中间一个回文串的位置，不妨设它是奇数长度（偶数类似）。

那么问题变成了求一个i和d使得1<=d<=r(i)且pre[i-d]和suf[i+d]为真。

枚举i，实际上就是问pre[i-r(i)..i-1]和suf[i+1..i+r(i)]取反后这两段有没有一个位置两者均为1，也就是and后不为0，暴力压位即可。

总时间复杂度为 $O (N^{2} / 32)$ 。

上午

T1代码：

//bzoj1801原题（mod数不一样而已） 
#include<cstdio>
#include<iostream>
#define mod 999983
using namespace std;
const int N=101;
int n,m;
long long ans,f[N][N][N];
long long C(long long t) {
    return (t*(t-1))>>1;
}
#define name "cannon"
int main(){
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    scanf("%d%d",&n,&m);
    f[0][0][0]=1;//f[i][j][k]表示前i行已经有j列有一个棋子，k列有两个棋子的方案数
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=m-j;k++){
                f[i][j][k]=f[i-1][j][k];//不放
                if(j) f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1);//一个棋子，放在原来没棋子的某一列上
                if(j<m&&k) f[i][j][k]+=f[i-1][j+1][k-1]*(j+1);//一个棋子，放在原来有一个棋子的某一列上
                if(j&&k) f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1);//两个棋子，一个在原来没棋子的列上，一个在原来一个棋子的列上
                if(j>1) f[i][j][k]+=f[i-1][j-2][k]*C(m-j-k+2);//两个棋子，都放在原来没棋子的列上
                if(j<=m-2&&k>1) f[i][j][k]+=f[i-1][j+2][k-2]*C(j+2);//两个棋子，都放在原来一个棋子的列上
                f[i][j][k]%=mod;
            }
        }
    }
    for(int i=0;i<=m;i++){
        for(int j=0;j<=m-i;j++){
            ans=(ans+f[n][i][j])%mod;
        }
    }   
    printf("%I64d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

T2代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+10;
const int M=1e3+10;
int tot,n,m,a[M],c[N/10],prime[N/10];
bool check[N];
void prepare(){//素数表 
    for(int i=2,t;i<=n;i++){
        if(!check[i]) prime[++tot]=i;
        for(int j=1;j<=tot&&(t=prime[j]*i)<=n;j++){
            check[t]=1;
            if(i%prime[j]==0) break;
        }
    }
}
void get1(int x){//指数+ 
    for(int i=1;i<=tot;i++){
        int r=x,p=prime[i];
        while(r) c[i]+=(r/=p);
    }
}
void get2(int x){//指数-
    for(int i=1;i<=tot;i++){
        int r=x,p=prime[i];
        while(r) c[i]-=(r/=p);
    }
}
void mul(int *a,int x){
    for(int i=1;i<=a[0];i++) a[i]*=x;
    for(int i=1;i<=a[0];i++){
        if(a[i]>9){
            a[i+1]+=a[i]/10;
            a[i]%=10;
        }
    }
    while(a[a[0]+1]){
        a[0]++;a[a[0]+1]+=a[a[0]]/10;a[a[0]]%=10;
    }
    if(a[0]>100) a[0]=100;//保留50位，运算到100位足够了 
}
int main(){
    freopen("rook.in","r",stdin);
    freopen("rook.out","w",stdout);
    scanf("%d%d",&n,&m);
    if(n<m) swap(n,m);
    a[0]=a[1]=1;
    prepare();
    get1(n);//加上n！的指数表达式 
    get2(m);get2(n-m);//减去m！和（n-m）!的指数表达式 
    for(int i=1;i<=tot;i++){
        for(int j=1;j<=c[i];j++){
            mul(a,prime[i]);//其实还可以+快速幂优化（嫌代码长，不写了……） 
        }
    }
    for(int i=min(a[0],50);i;i--) printf("%d",a[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
/*70分代码存档 
#include<cstdio>
#include<algorithm>
#define name "rook"
using namespace std;
const int N=1e7+10;
int n,m,len,f[N];
void mul(int x){
    for(int i=1;i<=len;i++) f[i]*=x;
    for(int i=1;i<=len;i++){
        if(f[i]>9){
            f[i+1]+=f[i]/10;
            f[i]%=10;
        }
    }
    for(;f[len+1];len++) f[len+2]+=f[len+1]/10,f[len+1]%=10;
}
void div(int x){
    for(int i=len;i;i--){
        f[i-1]+=f[i]%x*10;
        f[i]/=x;
    }
    for(int i=len;i;i--) if(f[i]){len=i;break;}
}
int main(){
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    f[len=1]=1;
    scanf("%d%d",&n,&m);
    if(n==m){puts("1");return 0;}
    if(n<m) swap(n,m);
    int cha=n-m;
    if(cha<m){
        for(int i=m+1;i<=n;i++) mul(i);
        for(int i=2;i<=cha;i++) div(i);
    }
    else{
        for(int i=cha+1;i<=n;i++) mul(i);
        for(int i=2;i<=m;i++) div(i);
    }
    for(int i=min(len,50);i;i--) printf("%d",f[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}*/

T3代码：

//非标程代码
#include<cstdio>
#include<iostream>
#define name "queen"
using namespace std;
int a[20];
int upperlim;
unsigned long long sum;
void NQueen(int row,int ld,int rd,int k){
    int pos,tpos,p,tp;
    if(row!=upperlim){
        pos=upperlim&~(row|ld|rd|a[k]);
        while(pos!=0) {
            p=pos&-pos;
            pos=pos-p;
            NQueen(row+p,(ld+p)<<1,(rd+p)>>1,k+1);
        }
    }
    else sum++;
}
int n,c,cnt;
int main(){
    //freopen("sh.txt","r",stdin);
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        a[i]=0;
        for(int j=0;j<n;j++){
            scanf("%d",&c);
            if(c==1){
                cnt++;
                a[i]+=(1<<j);
            }
        }
    }
    if(!cnt&&n==14){puts("365596");return 0;}
    if(!cnt&&n==15){puts("2279184");return 0;}
    if(!cnt&&n==16){puts("14772512");return 0;}
    upperlim=(1<<n)-1;
    sum=0;
    NQueen(0,0,0,0);
    cout<<sum;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

下午

T1代码：

//100% n<=1e9
#include<cstdio>
#define name "phi"
#define ll long long
#ifdef unix
#define LL "%lld"
#else
#define LL "%I64d"
#endif
using namespace std;
ll euler_phi(ll p){
    ll phi=p;
    for(ll i=2;i*i<=p;i++){
        if(!(p%i)){
            phi=phi-phi/i;
            while(!(p%i))
                p/=i;
        }
    }
    if(p>1)
        phi=phi-phi/p;
    return phi;
}
ll p;
int main(){
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    scanf(LL,&p);
    printf(LL,euler_phi(p));
    fclose(stdin);
    fclose(stdout);
    return 0;
}

T2代码：

/*
公式变形 F[n]=p1^(a1-1)*(p1-1) + p2^(a2-1)*(p2-1) + ....
Dfs 每个 p a 
如果剩下一项 p-1 p是素数 就不用再分解了  
可以特判掉 判断比较大的数是不是素数 这里用的 Miller Rabin 或者 Fermat
这不是重点 说不定sqrt暴力判常熟写的小一点也能过 没试过233 

还有一点就是 为什么 x+1>prime[num]的时候才直接放进去
一开始认为的是防止小的多次统计 但是去重之后答案还是不对
似乎还有什么没有想到的  欢迎大神留言 
*/
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
const ll N=1e7;
const ll M=1e5+10;
ll n,k,tot,prime[N/10],ans[M];
bool check[N+10];
void prepare(){
    ll x=min(N,n*100);
    for(ll i=2,t;i<=x;i++){
        if(!check[i]) prime[++tot]=i;
        for(ll j=1;j<=tot&&(t=prime[j]*i)<=x;j++){
            check[t]=1;
            if(i%prime[j]==0) break;
        }
    }
}
ll mul(ll x,ll y,ll z){
    ll r=0;
    for(;y;x<<=1,x%=z,y>>=1) if(y&1) r+=x,r%=z,y--;
    return r;
}
ll Qc(ll x,ll y,ll z){
    ll r=1;
    for(;y;y>>=1,x=mul(x,x,z)) if(y&1) r=mul(r,x,z);
    return r;
}
bool is_prime(ll n){
    if(n<2) return 0;
    if(n==2) return 1;
    if(!(n&1)) return 0;
    ll m=n-1,j=0;
    for(;!(m&1);j++,m>>=1);
    for(ll a,x,y,i=1;i<=5;i++){
        a=rand()%(n-1)+1;
        x=Qc(a,m,n);
        for(ll k=1;k<=j;k++){
            y=mul(x,x,n);
            if(y==1&&x!=1&&x!=n-1) return 0;
            x=y;
        }
        if(x!=1) return 0;
    }
    return 1;
}
void dfs(ll x,ll y,ll z){
    if(x==1){
        ans[++ans[0]]=y;return ;
    }
    if(z<=0) return ;
    if(x+1>prime[tot]&&is_prime(x+1)) ans[++ans[0]]=y*(x+1);// ?????不懂 
    for(ll a,b,c,i=z;i;i--){
        if(x%(prime[i]-1)==0){
            a=x/(prime[i]-1);b=y;c=1;
            while(a%c==0){
                b*=prime[i];
                dfs(a/c,b,i-1);
                c*=prime[i];
            }
        }
    }
}
#define name "arc"
int main(){
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    srand(time(0));
    scanf("%I64d%I64d",&n,&k);
    prepare();
    dfs(n,1,tot);
    sort(ans+1,ans+ans[0]+1);
    for(int i=1;i<=k;i++) printf("%I64d ",ans[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

T3代码：

#include<cstdio>
#include<algorithm>
#pragma comment(linker,"/STACK:1024000,1024000")
using namespace std;
const int N=2e7;
int n,nn,mul,p[N/3],M[N+1];
bool check[N+1];
long long ans;
int get(int n){
    if(n<=nn) return M[n];
    int res=0;
    for(int i=2,j;i<=n;i=j+1){
        j=n/(n/i);
        res+=(j-i+1)*get(n/i);
    }
    return 1-res;
}
#define name "sum"
int main(){
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    scanf("%d",&n);
    M[1]=1;
    nn=min(n,N);
    for(int i=2;i<=nn;i++){
        if(!check[i]){p[++p[0]]=i;M[i]=-1;}
        for(int j=1;j<=p[0]&&(mul=p[j]*i)<=nn;j++){
            check[mul]=1;
            if(i%p[j]==0){M[mul]=0;break;} 
            M[mul]=-M[i];
        }
    }
    for(int i=1;i<=nn;i++) M[i]+=M[i-1];
    for(int i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        ans+=1LL*(get(j)-get(i-1))*(n/i)*(n/i+1)/2;
    }
    printf("%I64d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

晚上

T1代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker,"/STACK:10240000,10240000")
#define name "mod"
using namespace std;
int b[30],v[30],n,a,c,ans;
void dfs(int cur,int x,int len){
    if(x==0) ans=min(ans,len);
    if(cur==-1) return;
    dfs(cur-1,x,len);
    dfs(cur-1,x%b[cur],len+1);
}
int main(){
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&a);
        for(int i=0;i<n;i++) scanf("%d",&b[i]);
        sort(b,b+n);
        c=0;
        ans=30;
        dfs(n-1,a,0);
        printf("%d
",ans<30?ans:-1);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
/*40分（稳）+未知分（看RP） 
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<algorithm>
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
int T,tx,x,n,cnt,a[N];
int ans;
void go(){
    int j;
    do{
        tx=x;
        for(j=1;j<=cnt;j++){
            tx%=a[j];
            if(!tx) break;
        }
        if(!tx) ans=min(ans,j);
    }while(next_permutation(a+1,a+cnt+1));
    if(ans==inf) puts("-1");
    else printf("%d
",ans);
}
int main(){
    //freopen("sh.txt","r",stdin);
    srand(time(0));
    scanf("%d",&T);
    while(T--){
        ans=inf;
        scanf("%d%d",&n,&x);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        cnt=unique(a+1,a+n+1)-(a+1);
        if(cnt<9){go();continue;}
        for(int i=1,j;i<=1e5;i++){
            tx=x;
            for(j=1;j<=cnt;j++){
                tx%=a[j];
                if(!tx) break;
            }
            if(!tx) ans=min(ans,j);
            random_shuffle(a+1,a+cnt+1);
        }
        if(ans==inf) puts("-1");
        else printf("%d
",ans);
    }
    return 0;
}*/

T2代码：

//正解思路同NOIP2014 Day2 T3 
#include<cstdio>
#include<cstring>
using namespace std;
int T,n,i,j,k,p[22];
char a[1005][111];int l[1005];
bool pd(int x){for(int i=2;i*i<=x;i++)if(x%i==0)return 0;return 1;}
int P(int i,int x){int t=0;for(int j=1;j<=l[i];j++)t=(t*10+a[i][j]-'0')%x;return t;}
bool work(){
    for(int i=1;i<=20;i++)
    for(int j=2;j<n;j++)
    if(1LL*P(j-1,p[i])*P(j+1,p[i])%p[i]!=1LL*P(j,p[i])*P(j,p[i])%p[i])return 0;
    return 1;
}
int main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    for(int i=1,j=int(1e8);i<=20;i++){while(!pd(j))j++;p[i]=j;}
    for(scanf("%d",&T);T;T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%s",a[i]+1),l[i]=strlen(a[i]+1);
        bool zero=0;
        for(int i=1;i<=n;i++)
        if(l[i]==1&&a[i][1]=='0')zero=1;
        if(zero){printf("No
");continue;}
        printf("%s
",work()?"Yes":"No");
    }
    fclose(stdin);
    fclose(stdout);
    return 0; 
}
/*80分代码备份 % 运算写炸了 
#include<cstdio>
#include<cstring>
#include<iostream>
#define name "sequence"
using namespace std;
const int maxn = 10005;
struct bign {
    int len, num[maxn];
    bign () {
        len = 0;
        memset(num, 0, sizeof(num));
    }
    bign (int number) {*this = number;}
    bign (const char* number) {*this = number;}
    void delzero ();
    void Put ();
    void operator = (int number);
    void operator = (char* number);
    bool operator <  (const bign& b) const;
    bool operator >  (const bign& b) const { return b < *this; }
    bool operator <= (const bign& b) const { return !(b < *this); }
    bool operator >= (const bign& b) const { return !(*this < b); }
    bool operator != (const bign& b) const { return b < *this || *this < b;}
    bool operator == (const bign& b) const { return !(b != *this); }
    void operator ++ ();
    void operator -- ();
    bign operator + (const int& b);
    bign operator + (const bign& b);
    bign operator - (const int& b);
    bign operator - (const bign& b);
    bign operator * (const int& b);
    bign operator * (const bign& b);
    bign operator / (const int& b);
    int operator % (const int& b);
};
const int maxm = 105;
int N;
char s[maxm];
bign A[maxm], zero = 0;
bool judge () {
    int c = 0;
    for (int i = 0; i < N; i++) if (A[i] == zero) c++;
    if (c) return c == N;
    for (int i = 1; i < N-1; i++)
        if (A[i-1] * A[i+1] != A[i] * A[i]) return false;
    return true;
}
int main () {
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            scanf("%s", s);
            A[i]=s;
        }
        if(A[0]==zero){puts("No");continue;}
        printf("%s
", judge() ? "Yes" : "No");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void bign::delzero () {
    while (len && num[len-1] == 0)
        len--;
    if (len == 0) {
        num[len++] = 0;
    }
}
void bign::Put () {
    for (int i = len-1; i >= 0; i--) 
        printf("%d", num[i]);
}
void bign::operator = (char* number) {
    len = strlen (number);
    for (int i = 0; i < len; i++)
        num[i] = number[len-i-1] - '0';
    delzero ();
}
void bign::operator = (int number) {
    len = 0;
    while (number) {
        num[len++] = number%10;
        number /= 10;
    }
    delzero ();
}
bool bign::operator < (const bign& b) const {
    if (len != b.len)
        return len < b.len;
    for (int i = len-1; i >= 0; i--)
        if (num[i] != b.num[i])
            return num[i] < b.num[i];
    return false;
}
void bign::operator ++ () {
    int s = 1;
    for (int i = 0; i < len; i++) {
        s = s + num[i];
        num[i] = s % 10;
        s /= 10;
        if (!s) break;
    }
    while (s) {
        num[len++] = s%10;
        s /= 10;
    }
}
void bign::operator -- () {
    if (num[0] == 0 && len == 1) return;
    int s = -1;
    for (int i = 0; i < len; i++) {
        s = s + num[i];
        num[i] = (s + 10) % 10;
        if (s >= 0) break;
    }
    delzero ();
}
bign bign::operator + (const int& b) {
    bign a = b;
    return *this + a;
}
bign bign::operator + (const bign& b) {
    int bignSum = 0;
    bign ans;
    for (int i = 0; i < len || i < b.len; i++) {
        if (i < len) bignSum += num[i];
        if (i < b.len) bignSum += b.num[i];
        ans.num[ans.len++] = bignSum % 10;
        bignSum /= 10;
    }
    while (bignSum) {
        ans.num[ans.len++] = bignSum % 10;
        bignSum /= 10;
    }
    return ans;
}
bign bign::operator - (const int& b) {
    bign a = b;
    return *this - a;
}
bign bign::operator - (const bign& b) {
    int bignSub = 0;
    bign ans;
    for (int i = 0; i < len || i < b.len; i++) {
        bignSub += num[i];
        bignSub -= b.num[i];
        ans.num[ans.len++] = (bignSub + 10) % 10;
        if (bignSub < 0) bignSub = -1;
        else bignSub = 0;
    }
    ans.delzero ();
    return ans;
}
bign bign::operator * (const int& b) {
    int bignSum = 0;
    bign ans;
    ans.len = len;
    for (int i = 0; i < len; i++) {
        bignSum += num[i] * b;
        ans.num[i] = bignSum % 10;
        bignSum /= 10;
    }
    while (bignSum) {
        ans.num[ans.len++] = bignSum % 10;
        bignSum /= 10;
    }
    return ans;
}
bign bign::operator * (const bign& b) {
    bign ans;
    ans.len = 0; 
    for (int i = 0; i < len; i++){  
        int bignSum = 0;  
        for (int j = 0; j < b.len; j++){  
            bignSum += num[i] * b.num[j] + ans.num[i+j];  
            ans.num[i+j] = bignSum % 10;  
            bignSum /= 10;
        }  
        ans.len = i + b.len;  
        while (bignSum){  
            ans.num[ans.len++] = bignSum % 10;  
            bignSum /= 10;
        }  
    }  
    return ans;
}
bign bign::operator / (const int& b) {
    bign ans;
    int s = 0;
    for (int i = len-1; i >= 0; i--) {
        s = s * 10 + num[i];
        ans.num[i] = s/b;
        s %= b;
    }
    ans.len = len;
    ans.delzero ();
    return ans;
}
int bign::operator % (const int& b) {
    bign ans;
    int s = 0;
    for (int i = len-1; i >= 0; i--) {
        s = s * 10 + num[i];
        ans.num[i] = s/b;
        s %= b;
    }
    return s;
}*/
/*
40分代码备份 
#include<cstdio>
#include<iostream>
#define name "sequence"
#define ll long long
#ifdef unix
#define LL "%lld"
#else
#define LL "%I64d"
#endif
//#pragma comment(linker,"/STACK:10240000,10240000")
using namespace std;
const int n=1e3+10;
int n,T;
bool flag;
ll tmp1,tmp2,a[n];
int main(){
    //freopen("sh.txt","r",stdin);
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf(LL,&a[i]);
        if(n<3){puts("Yes");continue;}
        flag=1;
        for(int i=2;i<n;i++){
            tmp1=a[i-1]*a[i+1];
            tmp2=a[i]*a[i];
            if(tmp1^tmp2){flag=0;break;}
        }
        puts(flag?"Yes":"no");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}*/

T3代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define name "palindromes"
using namespace std;
const int maxn=1e5+10;
char s[maxn],a[maxn*2];
int c1[maxn*2],c2[maxn*2];
int r[maxn*2],len; 
void Manacher(){
    int l=0;
    a[l++]='$';
    a[l++]='#';
    for(int i=0;i<len;i++){
        a[l++]=s[i];
        a[l++]='#';
    }
    a[l]=0;
    int mx=0,id=0;
    for(int i=0;i<l;i++){
        r[i]=mx>i?min(r[2*id-i],mx-i):1;
        while(a[i+r[i]]==a[i-r[i]]) r[i]++;
        if(i+r[i]>mx){
            mx=i+r[i];
            id=i;
        }
    }
}
int main(){
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s",s);
        len=strlen(s);
        Manacher();
        int l1=0,l2=0;
        for(int i=1;i<2*len+2;i++){
            if(r[i]==i&&i!=1) c1[++l1]=i-1+r[i];
            if(r[i]==2*len+2-i&&i!=2*len+1) c2[++l2]=i-(r[i]-1);
        }
        int flag=1;
        for(int i=l1;i>=1&&flag;i--){
            for(int j=1;j<=l2&&flag;j++){
                int ll=c1[i]+1;
                int rr=c2[j]-1;
                if(ll>rr) continue;
                int tmp=(rr+ll)/2;
                if(r[tmp]-1==0)continue;
                if(r[tmp]>=(rr-ll+2)/2) flag=0;
            }
        }
        if(flag) puts("No");
        else puts("Yes");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

上午

noip模拟题day1
——棋盘上的问题

day1模拟题 By FancyCoder
总览(Overview)
注意事项：
共3道题目，时间2.5小时。
Pascal选手允许使用math库和ansistring。
C++选手开放使用STL。
允许使用64位整型(int64或long long)。

题目名称炮车皇后
程序名 cannon rook queen
输入文件名 cannon.in rook.in queen.in
输出文件名 cannon.out rook.out queen.out
测试点数目 10 10 10
测试点分值 10 10 10
时间限制 1s 1s 1s
空间限制 128M 128M 128M
题目类型传统题传统题传统题

　

炮(cannon)
【题目描述】
众所周知，双炮叠叠将是中国象棋中很厉害的一招必杀技。炮吃子时必须
隔一个棋子跳吃，即俗称“炮打隔子”。炮跟炮显然不能在一起打起来，于是rly
一天借来了许多许多的炮在棋盘上摆了起来……他想知道，在N×M的矩形方格
中摆若干炮（可以不摆）使其互不吃到的情况下方案数有几种。
棋子都是相同的。
【输入说明】
一行，两个正整数N和M。
【输出说明】
一行，输出方案数mod 999983。
【样例输入】
1 3
【样例输出】
7
【数据范围】
对于40%的数据,N<=4,M<=4
对于70%的数据,N<=100,M<=8
对于100%的数据,N<=100,M<=100

车(rook)
【题目描述】
众所周知，车是中国象棋中最厉害的一子之一，它能吃到同一行或同一列
中的其他棋车。车跟车显然不能在一起打起来，于是rly一天又借来了许多许多
的车在棋盘上摆了起来……他想知道，在N×M的矩形方格中摆最多个数的车使
其互不吃到的情况下方案数有几种。但是，由于上次摆炮摆得实在太累，他为
了偷懒，打算增加一个条件：对于任何一个车A，如果有其他一个车B在它的上
方（车B行号小于车A），那么车A必须在车B的右边（车A列号大于车B）。
棋子都是相同的。
【输入说明】
一行，两个正整数N和M。
【输出说明】
一行，输出方案数的末尾50位（不足则直接输出）。
【样例输入】
2 2
【样例输出】
1
【数据范围】
对于20%的数据， N<=10， M<=10。
对于40%的数据， N<=40， M<=40。
对于70%的数据， N<=10000， M<=10000。
对于100%的数据， N<=1000000， M<=1000000。

皇后(queen)
【题目描述】
众所不知， rly现在不会玩国际象棋。但是，作为一个OIer， rly当然做过八
皇后问题。这里再啰嗦几句，皇后可以攻击到同行同列同对角线，在n*n的方格
中摆n个皇后使其互不攻击到，求不同的解的数量，这就是经典的n皇后问题。
现在问题推广到n皇后问题，这个问题对于你而言实在是小菜一叠。但因为上一
次rly把棋盘弄破了，又拿不出新的，所以rly打算难一点点，问题就是破棋盘上
的n皇后问题。他想知道……（你们懂的）。
棋子都是相同的。
【输入说明】
一行，一个正整数N。
接下来N行，每行N个数，要么为0，表示没坏，要么1，表示坏了。
【输出说明】
一行，输出不同的解的数量。
【样例输入】
4
1 0 1 1
1 1 1 0
0 1 1 1
1 1 0 1
【样例输出】
1
【数据范围】
对于40%的数据， N<=13。
对于100%的数据， N<=16。
其中有30%的数据，棋盘没有破（你可以认为rly又去买了一个新的）。

下午

晚上

noip模拟题day1

总览(Overview)

题目名称	取模	等比数列	回文串
程序名	mod	sequence	palindromes
输入文件名	mod.in	sequence.in	palindromes.in
输出文件名	mod.out	sequence.out	palindromes.out
时间限制	1s	1s	2s
空间限制	128M	128M	128M
题目类型	传统题	传统题	传统题

取模(mod)

【题目描述】

有一个整数a和n个整数b_1, …, b_n。在这些数中选出若干个数并重新排列，得到c_1,…, c_r。我们想保证a mod c_1 mod c_2 mod … mod c_r=0。请你得出最小的r，也就是最少要选择多少个数字。如果无解，请输出-1.

【输入说明】

输入文件的第一行有一个正整数T，表示数据组数。

接下去有T组数据，每组数据的第一行有两个正整数n和a.

第二行有n个正整数b_1, …, b_n.

【输出说明】

一行，输出答案。

【样例输入】

2 9

2 7

2 9

6 7

【样例输出】

-1

【数据范围】

对于40%的数据,n<=8

对于100%的数据,T<=5,n<=20,1 <=a <=10^6,b_i<=10^6

等比数列(sequence)

【题目描述】

判断一个数列是否为等比数列。

等比数列的定义为能被表示成a,aq,aq^2,aq^3...的数列，其中a和q不等于0。

【输入说明】

输入文件的第一行有一个正整数T，表示数据组数。

接下去有T组数据，每组数据的第一行一个整数n，接下来第二行n个数非负整数Ai，表示数列。

【输出说明】

对于每一个组的每个数据输出单独一行Yes或者No。

【样例输入】

1 1 1

1 4 2

【样例输出】

Yes

【数据范围】

对于40%的数据 0<=Ai<=10^9

对于100％的数据 T<=5,n<=1000,0<=Ai<=10^100

回文串(palindromes)

【题目描述】

判断是否能将字符串S分成三段非空回文串。

【输入说明】

第一行一个整数T，表示数据组数。

对于每一个组，仅包含一个由小写字母组成的串。

【输出说明】

对于每一组，单行输出"Yes" 或 "No"。

【样例输入】

abc

abaadada

【样例输出】

Yes

【数据范围】

对于40%的数据，|S|<=100

对于60%的数据，|S|<=1000

对于100%的数据，T<=20，|S|<=20000