题面
Description
用m种字母构造一个长度为n的字符串，如果一个字符串的字母重组后可以形成一个回文串则该串合法，问随机构成的长为n的字符串的合法子串数目期望值.
Input
第一行一整数T表示用例组数，每组用例输入两个整数n,m(1≤n,m≤2000).
Output
问构成的字符串的合法子串数目期望值，结果乘m^n后模10^9+7.
题解
万幸它乘了个m^n，刚好把期望中的m^-n消去了。
考虑到合法字串的特征，它必须最多只有一种字母出现奇数次，其余出现偶数次，那我们分子串长度为奇偶（即，是否有字母出现奇数次）两种情况讨论。
奇的生成函数:
二项式展开：
最终的答案还要考虑其在母串中的出现次数
偶的生成函数:
二项式展开：
最终的答案考虑其在母串中的出现次数
把组合数和幂都预处理，最终复杂度
ＣＯＤＥ
大常数TLE的代码QAQ
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
//优化
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<algorithm>
#define LL long long
#define MAXN 105
#define rg register
#define DB double
using namespace std;
inline int read() {
int f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}
while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}
return x * f;
}
int mod = 1000000007ll;
inline int qkpow(int a,int b) {
int res = 1;
while(b) {
if(b&1) res = 1ll*res*a % mod;
a = 1ll*a*a % mod;
b>>=1;
}
return res % mod;
}
int n,m,q,i,j,s,o,k,t;
int c[2005][2005];
int po[4010][2005];
int dp[2005],inv2 = qkpow(2,mod-2),inv2m[2005];
bool f[2005];
inline int POW(int i,int j) {
return po[i + 2000][j];
}
int main() {
c[0][0] = 1ll;inv2m[0] = 1ll;
for(rg int i = 1;i <= 2000;++ i) {
c[i][0] = c[i][i] = 1ll;
for(rg int j = 1;j < i;++ j) c[i][j] = (0ll + c[i-1][j]+c[i-1][j-1]) % mod;
inv2m[i] = (LL)inv2m[i-1]*inv2%mod;
}
for(rg int i = 0;i <= 4002;++ i) {
po[i][0] = 1ll;
for(rg int j = 1;j <= 2000;++ j) {
po[i][j] = ((LL)po[i][j-1]*(i-2000ll) + mod) % mod;
}
}
rg int T = read();
while(T--) {
n = read();m = read();
int AS = 0;
for(rg int i = 1;i <= n;++ i) {
if(i&1) {
int ans = (LL)inv2m[m] * (n - i + 1ll) % mod * POW(m,n-i) % mod * m % mod;
int ans2 = 0;
for(rg int j = 0;j < m;++ j) {
ans2 = (0ll+ans2 + mod + (POW((j<<1)+2-m,i) + mod - POW((j<<1)-m,i) + mod) * c[m-1][j] % mod) % mod;
}
ans = (LL)ans * ans2 % mod;
AS = (0ll + AS + mod + ans) % mod;
}
else {
int ans = (LL)inv2m[m] * (n - i + 1ll) % mod * POW(m,n-i) % mod;
int ans2 = 0;
for(rg int j = 0;j <= m;++ j) {
ans2 = (0ll+ans2 + mod + ((LL)POW((j<<1)-m,i) + mod) * c[m][j] % mod) % mod;
}
ans = (LL)ans * ans2 % mod;
AS = (0ll + AS + mod + ans) % mod;
}
}
printf("%d\n",AS);
}
return 0;
}
