//0MS 1500K//母函数。。背包、DP都行。。#include#include typedef long long LL;const int N=122;int n,f[N],tmp[N];int main(){ while(~scanf("%d",&n)) { memset(f,0,sizeof f), f[0]=1;//or 离线，对n排序。 for(int i=1; i<=n; ++i) f[i]=1; for(int i=2; i<=n; ++i) { memset(tmp,0,sizeof tmp); for(int j=0; j<=n; ++j) for(int k=0; j+k<=n; k+=i) tmp[j+k]+=f[j]; memcpy(f,tmp,sizeof f); } printf("%d\n",f[n]); } return 0;}
//0MS 1512K#include#include const int N=303;int n,f[N],tmp[N]; //平方数。。实际方案数也不是那么多。void Init(){ n=300;//N=300不是17*17。。 for(int i=0; i<=n; ++i) f[i]=1; for(int i=2; i<=17; ++i) { memset(tmp,0,sizeof tmp); for(int j=0; j<=n; ++j) for(int k=0; j+k<=n; k+=i*i) tmp[j+k]+=f[j]; memcpy(f,tmp,sizeof f); }}int main(){ Init(); while(scanf("%d",&n),n) printf("%d\n",f[n]); return 0;}
//46MS 1572K#include#include #include const int N=8008,v[5]={0,1,2,5};int n,f[N],tmp[N],num[5];int main(){ while(scanf("%d%d%d",&num[1],&num[2],&num[3]),num[1]||num[2]||num[3]) { n=1*num[1]+2*num[2]+5*num[3]; memset(f,0,sizeof f), f[0]=1; for(int las=0,nxt,i=1; i<=3; ++i) { memset(tmp,0,sizeof tmp), nxt=std::min(las+v[i]*num[i],n); for(int j=0; j<=las; ++j) for(int k=0; k<=num[i]/*&&j+k*v[i]<=nxt*/; ++k) tmp[j+k*v[i]]+=f[j]; memcpy(f,tmp,sizeof f), las=nxt; } bool flag=1; for(int i=1; i<=n; ++i) if(!f[i]) {printf("%d\n",i), flag=0; break;} if(flag) printf("%d\n",n+1); } return 0;}
//0MS 1524K#include#include #include const int N=13;int n,m,num[N],fac[N];double f[N],tmp[N];int main(){ fac[0]=1; for(int i=1; i<=11; ++i) fac[i]=fac[i-1]*i; while(~scanf("%d%d",&n,&m)) { for(int i=1; i<=n; ++i) scanf("%d",&num[i]); memset(f,0,sizeof f); for(int i=0; i<=num[1]; ++i) f[i]=1.0/fac[i]; for(int i=2; i<=n; ++i) { memset(tmp,0,sizeof tmp); for(int j=0; j<=m; ++j) if(f[j]) for(int k=0; k<=num[i]&&j+k<=m; ++k) tmp[j+k]+=f[j]/(double)fac[k];//要乘的系数为1/k! memcpy(f,tmp,sizeof f); } printf("%.0lf\n",1.0*fac[m]*f[m]);//f:组合数 } return 0;}
\(Description\)
求满足下列条件的长为\(n\)的字符串个数。
条件： 1.仅由'A','B','C','D'构成； 2.'A','C'出现偶数次（也可以不出现）。\(Solution\)
尝试用母函数表示，实际是要求\[(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\ldots)^2(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\ldots)^2\]
由\[\begin{aligned}e^x&=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\ldots\\e^{-x}&=1-x+\frac{x^2}{2!}-\frac{x^3}{3!}+\ldots\end{aligned}\]
可得\[\begin{aligned} 原式&=e^{2x}\left[\frac{1}{2}(e^x+e^{-x})\right]^2\\ &=\frac{1}{4}(e^{4x}+2e^{2x}+1)\\ &=\frac{1}{4}\left[1+4x+\frac{(4x)^2}{2!}+\frac{(4x)^3}{3!}+\ldots+1+2\times2x+\frac{2\times(2x)^2}{2!}+\frac{2\times(2x)^3}{3!}+\ldots+1\right]\\ &=\frac{1}{4}\sum_{n=0}^{\infty}[4^n+2\times2^n]\frac{x^n}{n!} \end{aligned}\] 还有个第三个式子化出来的\(1\)给省掉了。它应该是只对\(n=0\)有贡献吧。。 这就是指数型母函数的形式。于是第\(n\)项系数即为\[\begin{aligned}a_n&=\frac{1}{4}(4^n+2\times2^n)\\&=4^{n-1}+2^{n-1}\end{aligned}\]//0MS 1576K#include#include #define mod (100)#define gc() getchar()inline long long read(){ long long now=0;register char c=gc(); for(;!isdigit(c);c=gc()); for(;isdigit(c);now=now*10+c-'0',c=gc()); return now;}inline int FP(int x,long long k){ int t=1; for(; k; k>>=1, x=x*x%mod) if(k&1) t=t*x%mod; return t;}int main(){ int T; long long n; while(T=read(),T){ for(int Case=1; Case<=T; ++Case) n=read(), printf("Case %d: %d\n",Case,(FP(4,n-1)+FP(2,n-1))%mod); putchar('\n'); } return 0;}