程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu3658(矩陣快速冪)

hdu3658(矩陣快速冪)

編輯:關於C++

題意:

給出一個序列的長度;

這個序列只能有A-Z,a-z;

而且要求相鄰的字母asiic 碼差值小於等於32;而且必須有一個是等於32的;

問有種排列;

 

思路:

構造一個52  * 52的矩陣,把每個字母後面能跟哪些標為1;

然後矩陣快速冪;

然後再把差值為32的標志為0,在算一次(這樣算出來的就是肯定不會有差值等於32的)

兩次結果相減;

 

 

#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);
	}
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved