NOI2007这道题人类进化更完全之后出现了新的做法
毕姥爷题解：
于是毕姥爷出了一道环形版的这题（test0814），让我们写这个做法
环形的情况下，k=5的时候是162阶递推。
求这个递推可以用BM算法
1 //Achen
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdlib>
6 #include<vector>
7 #include<cstdio>
8 #include<queue>
9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int p=65521;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int k;
20
21 template<typename T>void read(T &x) {
22 char ch=getchar(); x=0; T f=1;
23 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
24 if(ch=='-') f=-1,ch=getchar();
25 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
26 }
27
28 LL a[1007][1007];
29 LL solve(int n) {
30 LL rs=1,f=1;
31 For(i,1,n) For(j,1,n) a[i][j]=(a[i][j]+p)%p;
32 For(i,1,n) {
33 For(j,i+1,n) {
34 LL A=a[i][i],B=a[j][i],t;
35 while(B) {
36 t=A/B;
37 For(k,i,n) a[i][k]=(a[i][k]-t*a[j][k]%p+p)%p;
38 For(k,i,n) swap(a[i][k],a[j][k]);
39 A%=B; swap(A,B); f=-f;
40 }
41 }
42 rs=rs*a[i][i]%p;
43 }
44 if(f==-1) rs=p-rs;
45 return rs;
46 }
47
48 #define ANS
49 int main() {
50 #ifdef ANS
51 //freopen("shanghai.in","r",stdin);
52 freopen("biao.out","w",stdout);
53 #endif
54 read(k);
55 //printf("%d
",500-2*k);
56 int tot=0;
57 For(n,2*k+1,500) {
58 tot++;
59 For(i,1,n) For(j,i+1,n) if(min(abs(i-j),n-abs(i-j))<=k) {
60 a[i][i]++;
61 a[j][j]++;
62 a[i][j]--;
63 a[j][i]--;
64 }
65 LL rs=solve(n-1);
66 printf("%lld,",rs);
67 For(i,1,n) For(j,1,n) a[i][j]=0;
68 if(tot==162) break;
69 }
70 Formylove;
71 }
对于每个k用上面这个暴力打表，再用下面这个模板得出递推（ps,BM算法n越大越精确，当k=5,n只取到200时会得出90多阶的递推而不是162阶）
1 //Achen
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdlib>
6 #include<vector>
7 #include<cstdio>
8 #include<queue>
9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int N=2007,p=65521;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int n,cnt,fail[N];
20 vector<LL>f[N];
21 LL a[N],delta[N];
22
23 template<typename T>void read(T &x) {
24 char ch=getchar(); x=0; T f=1;
25 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
26 if(ch=='-') f=-1,ch=getchar();
27 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
28 }
29
30 LL ksm(LL a,LL b) {
31 LL rs=1,bs=a%p;
32 while(b) {
33 if(b&1) rs=rs*bs%p;
34 bs=bs*bs%p;
35 b>>=1;
36 }
37 return rs;
38 }
39
40 #define ANS
41 int main() {
42 #ifdef ANS
43 freopen("biao.out","r",stdin);
44 freopen("k4.out","w",stdout);
45 #endif
46 read(n);
47 For(i,1,n) read(a[i]);
48 For(i,1,n) {
49 LL tp=0;
50 int up=f[cnt].size();
51 For(j,0,up-1)
52 tp=(tp+f[cnt][j]*a[i-j-1]%p)%p;
53 if(tp==a[i]) continue;
54 delta[i]=(a[i]-tp+p)%p;
55 fail[cnt]=i;
56 ++cnt;
57 if(cnt==1) {
58 f[cnt].resize(i);
59 continue;
60 }
61 LL mul=delta[i]*ksm(delta[fail[cnt-2]],p-2)%p,fmul=(p-mul)%p;
62 f[cnt].resize(i-fail[cnt-2]-1);
63 f[cnt].push_back(mul);
64 up=f[cnt-2].size();
65 For(j,0,up-1)
66 f[cnt].push_back(fmul*f[cnt-2][j]%p);
67 up=f[cnt-1].size();
68 if(f[cnt].size()<f[cnt-1].size()) f[cnt].resize(up);
69 For(j,0,up-1) f[cnt][j]=(f[cnt][j]+f[cnt-1][j])%p;
70 }
71 int up=f[cnt].size();
72 printf("%d
",up);
73 For(i,0,up-1) printf("%lld,",f[cnt][i]);
74 Formylove;
75 }
把打出来的表直接放程序里，暴力递推就有80了。
1 //Achen
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdlib>
6 #include<vector>
7 #include<cstdio>
8 #include<queue>
9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int p=65521;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int len[10]={0,2,6,18,54,162};
20 LL f[10][200]={{},{0,2,65520},{0,4,0,65511,0,4,65520},{0,4,8,18,65401,65269,65038,72,272,964,272,72,65038,65269,65401,18,8,4,65520},{0,6,15,0,30,62797,60175,64321,63502,7551,27432,56468,63447,45434,59589,49862,56027,40848,38206,22675,8556,3412,32492,56715,38363,45055,20818,27014,20818,45055,38363,56715,32492,3412,8556,22675,38206,40848,56027,49862,59589,45434,63447,56468,27432,7551,63502,64321,60175,62797,30,0,15,6,65520},{0,8,16,65511,304,1112,62517,8818,65348,42675,8648,3411,62664,34224,61359,23789,47033,9577,18774,26446,25242,2440,16835,19355,24778,54491,33418,44673,31664,47318,45699,57034,58329,16947,14821,37483,29701,44701,57248,45494,20917,51056,23909,32660,48089,10311,61927,58068,19461,11155,62649,39025,36755,38928,31565,26603,24094,10349,15499,13713,26713,29605,28753,24627,62639,16313,6983,45353,19779,57391,61923,7930,19732,34243,31283,21822,15252,63919,32152,22840,52349,39683,52349,22840,32152,63919,15252,21822,31283,34243,19732,7930,61923,57391,19779,45353,6983,16313,62639,24627,28753,29605,26713,13713,15499,10349,24094,26603,31565,38928,36755,39025,62649,11155,19461,58068,61927,10311,48089,32660,23909,51056,20917,45494,57248,44701,29701,37483,14821,16947,58329,57034,45699,47318,31664,44673,33418,54491,24778,19355,16835,2440,25242,26446,18774,9577,47033,23789,61359,34224,62664,3411,8648,42675,65348,8818,62517,1112,304,65511,16,8,65520}};
21 LL a[10][200]={{},{0,3,4},{0,125,384,1183,3528,10404,30250},{0,16807,17423,19038,4069,36749,10890,20559,13383,44811,44978,31152,53478,7585,61903,7694,36892,16182,32848},{0,65457,7500,44205,40188,48640,8405,785,15584,27550,24009,2806,39941,39586,12655,29060,63519,440,55231,44413,1719,61638,15338,1980,42275,50263,4780,56562,5966,13459,65345,34985,7721,23101,124,14839,52885,15175,36581,16396,48404,48035,17828,33918,65101,15000,2860,2388,63410,9605,50082,55806,49163,56598,63631},{0,43464,44962,35706,26874,2031,35703,14530,53646,61395,56708,29157,43858,3788,7056,41580,35556,22057,12105,25313,43903,43174,50192,48518,28112,37197,16270,49973,27582,18340,39356,28374,39671,33552,22814,29972,42427,19919,38723,24057,51493,6507,45387,18936,65511,31659,44915,62932,34532,65492,5505,65280,61430,9555,21382,18222,21311,853,52691,17163,48026,45847,22611,22383,30878,32423,7502,14151,47992,49564,36686,24946,21597,5702,10921,28206,39980,64500,34046,44791,42032,19696,32425,58579,50204,11055,40170,56738,14539,3621,56024,40757,56759,1895,3710,15280,40381,27494,42590,45942,46226,4201,64024,26768,41146,2839,57415,45261,18437,19547,34769,5118,1282,62750,31296,62980,42068,57199,26653,51220,13640,60680,16245,27774,54000,14218,38367,56167,56929,61021,33773,62448,58886,2385,24829,45945,46912,21640,18358,36563,28022,33944,42920,38354,47928,52596,36132,28846,50297,46818,25798,48043,58726,47491,31838,56042,32772,22166,49864,13935,19648,521,63481}};
22 LL b[10007],n,k;
23
24 template<typename T>void read(T &x) {
25 char ch=getchar(); x=0; T f=1;
26 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
27 if(ch=='-') f=-1,ch=getchar();
28 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
29 }
30
31 #define ANS
32 int main() {
33 #ifdef ANS
34 freopen("shanghai.in","r",stdin);
35 freopen("shanghai.out","w",stdout);
36 #endif
37 read(k); read(n);
38 For(i,1,len[k]) b[i+2*k]=a[k][i];
39 For(i,len[k]+2*k+1,n) {
40 For(j,1,len[k]) b[i]=(b[i]+f[k][j]*b[i-j]%p)%p;
41 }
42 printf("%lld
",b[n]);
43 Formylove;
44 }
45 /*
46
47 */
矩乘优化好像跑不过，得多项式取模优化才行。。。
时间复杂度k^2logn
1 //Achen 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdlib> 6 #include<vector> 7 #include<cstdio> 8 #include<queue> 9 #include<cmath> 10 #include<set> 11 #include<map> 12 #define Formylove return 0 13 #define For(i,a,b) for(int i=(a);i<=(b);i++) 14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 15 const int p=65521; 16 typedef long long LL; 17 typedef double db; 18 using namespace std; 19 int len[10]={0,2,6,18,54,162}; 20 LL f[10][200]={{},{0,2,65520},{0,4,0,65511,0,4,65520},{0,4,8,18,65401,65269,65038,72,272,964,272,72,65038,65269,65401,18,8,4,65520},{0,6,15,0,30,62797,60175,64321,63502,7551,27432,56468,63447,45434,59589,49862,56027,40848,38206,22675,8556,3412,32492,56715,38363,45055,20818,27014,20818,45055,38363,56715,32492,3412,8556,22675,38206,40848,56027,49862,59589,45434,63447,56468,27432,7551,63502,64321,60175,62797,30,0,15,6,65520},{0,8,16,65511,304,1112,62517,8818,65348,42675,8648,3411,62664,34224,61359,23789,47033,9577,18774,26446,25242,2440,16835,19355,24778,54491,33418,44673,31664,47318,45699,57034,58329,16947,14821,37483,29701,44701,57248,45494,20917,51056,23909,32660,48089,10311,61927,58068,19461,11155,62649,39025,36755,38928,31565,26603,24094,10349,15499,13713,26713,29605,28753,24627,62639,16313,6983,45353,19779,57391,61923,7930,19732,34243,31283,21822,15252,63919,32152,22840,52349,39683,52349,22840,32152,63919,15252,21822,31283,34243,19732,7930,61923,57391,19779,45353,6983,16313,62639,24627,28753,29605,26713,13713,15499,10349,24094,26603,31565,38928,36755,39025,62649,11155,19461,58068,61927,10311,48089,32660,23909,51056,20917,45494,57248,44701,29701,37483,14821,16947,58329,57034,45699,47318,31664,44673,33418,54491,24778,19355,16835,2440,25242,26446,18774,9577,47033,23789,61359,34224,62664,3411,8648,42675,65348,8818,62517,1112,304,65511,16,8,65520}}; 21 LL a[10][200]={{},{0,3,4},{0,125,384,1183,3528,10404,30250},{0,16807,17423,19038,4069,36749,10890,20559,13383,44811,44978,31152,53478,7585,61903,7694,36892,16182,32848},{0,65457,7500,44205,40188,48640,8405,785,15584,27550,24009,2806,39941,39586,12655,29060,63519,440,55231,44413,1719,61638,15338,1980,42275,50263,4780,56562,5966,13459,65345,34985,7721,23101,124,14839,52885,15175,36581,16396,48404,48035,17828,33918,65101,15000,2860,2388,63410,9605,50082,55806,49163,56598,63631},{0,43464,44962,35706,26874,2031,35703,14530,53646,61395,56708,29157,43858,3788,7056,41580,35556,22057,12105,25313,43903,43174,50192,48518,28112,37197,16270,49973,27582,18340,39356,28374,39671,33552,22814,29972,42427,19919,38723,24057,51493,6507,45387,18936,65511,31659,44915,62932,34532,65492,5505,65280,61430,9555,21382,18222,21311,853,52691,17163,48026,45847,22611,22383,30878,32423,7502,14151,47992,49564,36686,24946,21597,5702,10921,28206,39980,64500,34046,44791,42032,19696,32425,58579,50204,11055,40170,56738,14539,3621,56024,40757,56759,1895,3710,15280,40381,27494,42590,45942,46226,4201,64024,26768,41146,2839,57415,45261,18437,19547,34769,5118,1282,62750,31296,62980,42068,57199,26653,51220,13640,60680,16245,27774,54000,14218,38367,56167,56929,61021,33773,62448,58886,2385,24829,45945,46912,21640,18358,36563,28022,33944,42920,38354,47928,52596,36132,28846,50297,46818,25798,48043,58726,47491,31838,56042,32772,22166,49864,13935,19648,521,63481}}; 22 LL b[10007],n,k; 23 24 template<typename T>void read(T &x) { 25 char ch=getchar(); x=0; T f=1; 26 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); 27 if(ch=='-') f=-1,ch=getchar(); 28 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f; 29 } 30 31 LL rs[507],bs[507]; 32 void mul(LL a[],LL b[],LL c[]) { 33 static LL tp[507]; 34 int up=(len[k]<<1); 35 For(i,0,up) tp[i]=0; 36 For(i,0,len[k]-1) For(j,0,len[k]-1) 37 (tp[i+j]+=a[i]*b[j]%p)%=p; 38 Rep(i,up,len[k]) For(j,1,len[k]) 39 (tp[i-j]+=f[k][j]*tp[i]%p)%=p; 40 For(i,0,up) c[i]=tp[i]; 41 } 42 43 void ksm(LL b) { 44 while(b) { 45 if(b&1) mul(rs,bs,rs); 46 mul(bs,bs,bs); 47 b>>=1; 48 } 49 } 50 51 #define ANS 52 int main() { 53 #ifdef ANS 54 freopen("shanghai.in","r",stdin); 55 freopen("shanghai.out","w",stdout); 56 #endif 57 read(k); read(n); 58 n-=2*k; 59 For(i,1,len[k]) b[i]=a[k][i]; 60 if(n<=len[k]) printf("%lld ",b[n]); 61 else { 62 rs[0]=1; bs[1]=1; 63 ksm(n-1); 64 LL ans=0; 65 For(i,0,len[k]-1) (ans+=b[i+1]*rs[i]%p)%=p; 66 printf("%lld ",ans); 67 } 68 Formylove; 69 }