题意:

给出一个序列的长度;

这个序列只能有A-Z,a-z;

而且要求相邻的字母asiic 码差值小于等于32;而且必须有一个是等于32的;

问有种排列;

?

思路:

构造一个52 　*　52的矩阵，把每个字母后面能跟哪些标为１；

然后矩阵快速幂；

然后再把差值为３２的标志为０，在算一次（这样算出来的就是肯定不会有差值等于３２的）

两次结果相减；

?

?

#include
  
   
#include
   
     #define ll long long struct mat { ll g[60][60]; }res, ori; const ll MOD = 1e9 + 7; ll n; void init() { memset(ori.g ,0, sizeof(ori.g)); memset(res.g ,0, sizeof(res.g)); for(int i = 0; i < 26; i++) { for(int j = 0; j <= i + 26; j++) { ori.g[j][i] = 1; } } for(int i = 26; i < 52; i++) { for(int j = 51; j >= i - 26 ; j--) { ori.g[j][i] = 1; } } for(int i = 0; i < 52; i++) { res.g[0][i] = 1; } } mat mul(mat a, mat b) { mat tmp; memset(tmp.g, 0, sizeof(tmp.g)); for(int i = 0; i < 52; i++) { for(int j = 0; j < 52; j++) { for(int k = 0; k < 52; k++) { tmp.g[i][j] = (tmp.g[i][j] + a.g[i][k] * b.g[k][j])% MOD; } } } return tmp; } ll cul(ll k) { while(k) { if(k & 1) res = mul(res, ori); k >>= 1; ori = mul(ori, ori); } ll ans = 0; for(int i = 0; i < 52; i++) { ans = (ans + res.g[0][i]) % MOD; } return ans; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%lld",&n); init(); ll k1 = cul(n - 1); init(); for(int i = 0; i < 26; i++) { ori.g[i + 26][i] = 0; } for(int i = 26; i < 52; i++) { ori.g[i - 26][i] = 0; } ll k2 = cul(n - 1); printf("%lld\n",(k1 + MOD- k2) % MOD); } }
   
  

?