Math(CC PARSIN)

题目大意

给出m，n和一个两位小数x。 求 ∑k[1]+k[2]+...+k[m]=nΠmi=1sin(k[i]∗x) n<=10^9,m<=30

这题真的是道数学题

首先考虑一个简单的dp 设f[i][j]表示 i=∑jl=1k[l] 时所有情况的和 容易想到一个简单的转移 f[i][j]=∑ik=1f[i−l][j−1]∗sin(k∗x) 考虑当k[m]=1时对于f[n][m]的贡献为f[n-1][m-1]*sin(x) 当k[m]>1时呢 解数学题时间： 要用到几个常见的公式： sin(a+b)=sin(a)cos(b)+sin(b)*cos(a) cos(a+b)=cos(a)cos(b)-sin(a)sin(b) sin(a)^2+cos(a)^2=1 然后就可以手推了。。。 1式：sin(k∗x)=sin((k−1)x+x)=sin((k−2)x+2∗x) 由1式得2式：2sin(k∗x)=sin((k−1)x+x)+sin((k−2)x+2∗x) 3式：sin((k−1)x+x)=sin(x)cos((k−1)x)+cos(x)sin((k−1)x) 4式：sin((k−2)x+2∗x)=2sin(x)cos(x)cos((k−2)x)+(cos(x)2−sin(x)2)sin((k−2)x) =2sin(x)cos(x)∗cos((k−2)x)+2cos(x)2sin((k−2)x)+sin((k−2)x) 5式：sin(x)cos((k−1)x)=sin(x)cos((k−2)x+x))=sin(x)(cos((k−2)x)∗cos(x)−sin((k−2)x)∗sin(x)) 6式：cos(x)sin((k−1)x)=cos(x)sin((k−2)x+x)=cos(x)(sin(x)cos((k−2)x)+cos(x)sin((k−2)x)) 由3,5,6式得7式：sin((k−1)x+x)=sin(x)cos((k−1)x)+cos(x)sin((k−1)x) =sin(x)(cos((k−2)x)∗cos(x)−sin((k−2)x)∗sin(x))+cos(x)(sin(x)cos((k−2)x)+cos(x)sin((k−2)x)) =2sin(x)cos(x)cos((k−2)x)+cos(x)2sin((k−2)x−sin(x)2sin((k−2)x)) =2sin(x)cos(x)cos((k−2)x)+2cos(x)2sin((k−2)x)−sin((k−2)x) 由2,4,7式得8式：2sin(k∗x)=sin((k−1)x+x)+sin((k−2)x+2∗x) =4sin(x)cos(x)cos((k−2)x)+4cos(x)2sin((k−2)x)+2sin((k−2)x) 由8式得9式：sin(k∗x)=2sin(x)cos(x)cos((k−2)x)+2cos(x)2sin((k−2)x)+sin((k−2)x) =2cos(x)(sin(x)cos((k−2)x)+cos(x)sin((k−2)x))+sin((k−2)x)=2cos(x)sin((k−1)x)+sin((k−2)x) 终于，我们得到了一个不错的式子，通过这个式子可以发现k[m]>1时对f[n][m]的贡献为2cos(x)*f[n-1][m]+f[n-2][m] 然后就可以矩阵乘法了。 复杂度O(8*m^3log n)

代码

#include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #define fo(i,a,b) for(i=a;i<=b;i++) const int maxn=60+5; int i,j,n,m,t,k; struct ar{ double a[maxn][maxn]; } a,c; double x; ar ch(ar a,ar b){ ar c; memset(c.a,0,sizeof(c.a)); fo(i,1,m*2) fo(j,1,m*2) fo(k,1,m*2) c.a[i][j]=c.a[i][j]+a.a[i][k]*b.a[k][j]; return c; } int main(){ scanf("%d",&t); while (t){ t--; scanf("%d%d%lf",&m,&n,&x); memset(a.a,0,sizeof(a.a)); memset(c.a,0,sizeof(c.a)); fo(i,m+1,m*2){ a.a[i][i-m]=1,a.a[i-m][i]=-1; a.a[i][i]=2*cos(x);if (i<m*2)a.a[i][i+1]=sin(x); } c.a[1][1]=sin(x);c.a[1][m+1]=sin(2*x);c.a[1][m+2]=sin(x)*sin(x); n--; while (n){ if (n%2)c=ch(c,a); a=ch(a,a); n/=2; } double s=c.a[1][m]; if (s>0) printf("+");else printf("-"); s=fabs(s); if (s<1){ double s1=0.1; while (1) if (s>s1) {printf("%d\n",(int)(s/s1));break;}else s1*=0.1; }else{ while (s)if (s<10) {printf("%d\n",(int)s);break;}else s/=10; } } }