BZOJ 1009: [HNOI2008]GT考试 September 9, 2016 ###Description 阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为0 ###Input 第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000 ###Output 阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果. ###Sample Input 4 3 100 111 ###Sample Output 81 ###Solution 我们把不吉利的数字用s表示，用f[i][j]表示n[i]匹配到s[j]的情况数，则可以用一个转移矩阵a通过f[i-1][j]求出f[i][j] a[i][j]表示在s中匹配了i位时，在后面添数，有多少种情况匹配到j位，也就是指s的前i位后面添数后最长的公共前后缀长度为j的情况数 kmp预处理，然后对于每个i，枚举添加的数，再仿照kmp进行处理，即可求出转移矩阵 矩阵快速幂优化就可以过了，时间复杂度$$O(logN*M^3)$$ ###Code ```c++ #include<cstdio> struct _matrix { int s[21][21],a,b; _matrix() { for(int i=0;i<21;i++) for(int j=0;j<21;j++) s[i][j]=0; } }temp; int mod; void mul(_matrix &x,_matrix y) { for(int i=0;i<x.a;i++) for(int j=0;j<y.b;j++) { temp.s[i][j]=0; for(int k=0;k<x.b;k++) temp.s[i][j]+=x.s[i][k]*y.s[k][j]; temp.s[i][j]%=mod; } temp.a=x.a; temp.b=y.b; x=temp; } int m[21],n,f[21]; int main() { int mm; scanf("%d%d%d",&n,&mm,&mod); char t[20]; scanf("%s",t); for(int i=0;i<mm;i++)m[i+1]=t[i]-48; f[1]=0; for(int i=2;i<=mm;i++) { int t=i-1; while(t!=0&&m[f[t]+1]!=m[i])t=f[t]; if(t==0) { if(m[1]==m[i]) f[i]=1; else f[i]=0; } else { f[i]=f[t]+1; } } _matrix a; a.a=mm+1; a.b=mm+1; a.s[0][0]=9,a.s[0][1]=1; for(int i=1;i<mm;i++) { for(int j=0;j<10;j++) { if(m[i+1]==j) { a.s[i][i+1]++; continue; } int t=i; while(t!=0&&m[f[t]+1]!=j)t=f[t]; if(t==0) { if(m[1]==j) a.s[i][t+1]++; else a.s[i][0]++; } else a.s[i][f[t]+1]++; } } _matrix b; b.a=1; b.b=mm+1; b.s[0][0]=9; b.s[0][1]=1; int ans=0,to=n-1,no=1; while(no<to) { if(to&no)mul(b,a); mul(a,a); no<<=1; } for(int i=0;i<mm;i++)ans+=b.s[0][i]; printf("%d\n",ans%mod); return 0; } ```
BZOJ 1089: [SCOI2003]严格n元树 September 8, 2016 ###Description 如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d （根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为2的严格2元树有三个，如下图： ![1.jpg][1] 给出n, d，编程数出深度为d的n元树数目。 ###Input 仅包含两个整数n, d(0 < n <= 32, 0 <= d <= 16) ###Output 仅包含一个数，即深度为d的n元树的数目。 ###Sample Input 【样例输入1】 2 2 【样例输入2】 2 3 【样例输入3】 3 5 ###Sample Output 【样例输出1】 3 【样例输出2】 21 【样例输出2】 58871587162270592645034001 ###Solution 我们用f(d)表示深度不大于d的n元树数目，则答案为f(d)-f(d-1) 当深度为d时，可以看做一棵深度为1的n元树，每个叶子节点向下都有d(n-1)种可能，再加上深度为0的情况，可得出f(d)=f(d-1)^n+1 ###Code ```c++ #include<cstdio> #include<memory.h> #include<cstring> #define maxnum 100 #define cas 1000000000 int a[maxnum],b[maxnum],t[maxnum],al=1,bl; inline void mul() { memset(t,0,(al+bl+1)*4); for(int i=0;i<al;i++) for(int j=0;j<bl;j++) { long long f=(long long)a[i]*b[j]; t[i+j]+=f%cas; if(t[i+j]>=cas)t[i+j]-=cas,t[i+j+1]++; t[i+j+1]+=f/cas; if(t[i+j+1]>=cas)t[i+j+1]-=cas,t[i+j+2]++; } if(t[al+bl-1])al=al+bl;else al=al+bl-1; memcpy(a,t,al*4); } inline void print(int *a) { printf("%d",a[al-1]);for(int i=al-2;i>=0;i--)printf("%09d",a[i]);printf("\n"); } int main() { int n,d; scanf("%d%d",&n,&d); a[0]=1; while(d--) { memcpy(b,a,al*4); bl=al; for(int i=1;i<n;i++)mul(); a[0]++; for(int i=0;a[i]>=cas;i++)a[i]-=cas,a[i+1]++; if(a[al])al++; } for(int i=0;i<bl;i++)a[i]-=b[i]; for(int i=0;i<al;i++)if(a[i]<0)a[i]+=cas,a[i+1]--; if(!a[al-1])al--; print(a); printf("\n"); return 0; } ``` [1]: /usr/uploads/2016/09/1813884886.jpg
BZOJ 1002: [FJOI2007]轮状病毒 September 7, 2016 ###Description 轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示 ![bzoj1002.p1.png][1] N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不同的3轮状病毒，如下图所示 ![bzoj1002.p2.png][2] 现给定n(N<=100)，编程计算有多少个不同的n轮状病毒 ###Input 第一行有1个正整数n ###Output 计算出的不同的n轮状病毒数输出 ###Sample Input 3 ###Sample Output 16 ###Solution 这道题的正解是基尔霍夫矩阵，推出f[i]=f[i-1]*3-f[i-2]+2，然而我这等蒟蒻肯定是不知道怎么证的 下面是我的做法： 首先去掉外面的某条边，图就变成了类似于这样的结构： ![bzoj1002-1.png][3] 可行解就类似于下图： ![bzoj1002-2.png][4] 我们将未与中心节点相连的点标0，相连的标1，删去的边也标1，每个解就变成了一个01串 假设某个解最外面一共去掉k条边，那么这个01串长度为n+k-1，共有2k-1个1，而由于向上的边与删去的边交替出现，每个解一定与每个01串一一对应，所以最外层去掉k条边时，解的个数为 $$C(n+k-1,k\cdot 2-1)$$。 由于固定了某条边必须去掉，这里只求出了总情况数了k/n，所以还需要乘上n/k，最后的结果就是这样的： $$\sum_k^n C(n+k-1,k\cdot 2-1)\cdot\frac{n}{k}$$ 考虑到高精度大约要O(n)，时间复杂度O(n^3) 记录上一个 $$C(n+k-1,k\cdot 2-1)$$，可以优化到O(n^2) <del>然而这种数据范围为什么不打表。。</del> ###Code ```c++ #include<cstdio> #define cas 10000000 #define maxnum 100 int x[maxnum],y[maxnum],tmp[maxnum+1]; inline void mul(int a) { tmp[0]=0; for(int i=0;i<maxnum;i++) { y[i]*=a; y[i]+=tmp[i]; tmp[i+1]=y[i]/cas; y[i]%=cas; } } inline void div(int a) { for(int i=maxnum-1;i>=0;i--) { if(i)y[i-1]+=y[i]%a*cas; y[i]/=a; } } inline void c(int a,int b) { if(b>a/2)b=a-b; for(int i=0;i<maxnum;i++)y[i]=0; y[0]=1; for(int i=a;i>a-b;i--)mul(i); for(int i=2;i<=b;i++)div(i); } inline void print(int *k) { bool is0=true; for(int i=maxnum-1;i>=0;i--) { if(is0&&k[i]) { is0=false; printf("%d",k[i]); } else if(!is0) { printf("%07d",k[i]); } } } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { c(n+i-1,2*i-1); mul(n); div(i); for(int i=0;i<maxnum;i++) { x[i]+=y[i]; if(x[i]>cas)x[i]-=cas,x[i+1]++; } } print(x); return 0; } ``` [1]: /usr/uploads/2016/09/2454961388.png [2]: /usr/uploads/2016/09/212298548.png [3]: /usr/uploads/2016/09/3955661276.png [4]: /usr/uploads/2016/09/3098156740.png [5]: /usr/uploads/2016/09/1992184554.gif [6]: /usr/uploads/2016/09/1288349390.gif [7]: /usr/uploads/2016/09/1992184554.gif