题目大意：有$n(n\leqslant3500)$个人坐成一个环，$0$号手上有个球，每秒钟可以向左或向右传球，问$m$秒后球在$0$号手上的方案数。

题解：一个$O(nm)$的$DP$，$f_{i,j}=f_{i-1,j-1}+f_{i-1,j+1}$（$f_{i,j}$表示现在为第$i$秒，球在$j$号手上的方案数）。这样明显不可以通过。

生成函数，$x^i$对应为原环上第$|i|\bmod n$个人，于是发现$f_{i,m}=\sum\limits_{k\in\mathbb Z}[x^{i+kn}](x^{-1}+x)^m$，所以答案为$\sum\limits_{k\in\mathbb Z}[x^{kn}](x^{-1}+x)^m$。这样感觉不可做，但是把它变成循环卷积后，答案就是$[x^0](x^{n-1}+x)^m$，复杂度$O(n\log_2n\log_2m)$。

注意，模数为$10^9+7$，需要三模$NTT$

卡点：无

C++ Code：

#include 
     
      #include 
      
       #define maxn 3510const int mod = 1e9 + 7;namespace Math {	inline int pw(int base, int p, const int mod) {		static int res;		for (res = 1; p; p >>= 1, base = static_cast
       
         (base) * base % mod) if (p & 1) res = static_cast
        
          (res) * base % mod;		return res;	}	inline int inv(int x, const int mod) { return pw(x, mod - 2, mod); }}int n, m;namespace Poly {#define N 8192	inline void clear(register int *l, const int *r) {		if (l >= r) return ;		while (l != r) *l++ = 0;	}	template 
         
           struct P {		int lim, s, rev[N];		int Wn[N | 1];		inline void reduce(int &x) { x += x >> 31 & mod; }		inline void init(int n) {			lim = 1, s = -1; while (lim < n) lim <<= 1, ++s;			for (register int i = 1; i < lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;			const int t = Math::pw(G, (mod - 1) / lim, mod);			*Wn = 1; for (register int *i = Wn; i != Wn + lim; ++i) *(i + 1) = static_cast
          
            (*i) * t % mod; } inline void NTT(int *A, const int op = 1) { for (register int i = 1; i < lim; ++i) if (i < rev[i]) std::swap(A[i], A[rev[i]]); for (register int mid = 1; mid < lim; mid <<= 1) { const int t = lim / mid >> 1; for (register int i = 0; i < lim; i += mid << 1) { for (register int j = 0; j < mid; ++j) { const int W = op ? Wn[j * t] : Wn[lim - j * t]; const int X = A[i + j], Y = static_cast
           
             (A[i + j + mid]) * W % mod; reduce(A[i + j] += Y - mod), reduce(A[i + j + mid] = X - Y); } } } if (!op) { const int ilim = Math::inv(lim, mod); for (register int *i = A; i != A + lim; ++i) *i = static_cast
            
              (*i) * ilim % mod; } } int res[N]; inline int operator [] (const int i) { return res[i]; } int C[N], D[N]; void MUL(int *A, int *B) { std::copy(A, A + n, C), clear(C + n, C + lim); std::copy(B, B + n, D), clear(D + n, D + lim); NTT(C), NTT(D); for (int i = 0; i < lim; i++) res[i] = static_cast
             
               (C[i]) * D[i] % mod; NTT(res, 0); } void SQR(int *A) { std::copy(A, A + n, C), clear(C + n, C + lim); NTT(C); for (int i = 0; i < lim; i++) res[i] = static_cast
              
                (C[i]) * C[i] % mod; NTT(res, 0); } } ; const int mod1 = 469762049, mod2 = 998244353, mod3 = 1004535809; const long long mod_1_2 = static_cast
               
                 (mod1) * mod2; const int inv_1 = Math::inv(mod1, mod2), inv_2 = Math::inv(mod_1_2 % mod3, mod3); P
                
                  P1; P
                 
                   P2; P
                  
                    P3; inline int get(const int A, const int B, const int C) { const long long x = static_cast
                   
                     (B - A + mod2) % mod2 * inv_1 % mod2 * mod1 + A; return (static_cast
                    
                      (C - x % mod3 + mod3) % mod3 * inv_2 % mod3 * (mod_1_2 % mod) % mod + x) % mod; } inline void reduce(int &x) { x += x >> 31 & mod; } inline void init(int n) { P1.init(n), P2.init(n), P3.init(n); } void MUL(int *A, int *B) { P1.MUL(A, B), P2.MUL(A, B), P3.MUL(A, B); for (int i = 0; i < n + n; i++) reduce(A[i] = get(P1[i], P2[i], P3[i]) + get(P1[i + n], P2[i + n], P3[i + n]) - mod); } void SQR(int *A) { P1.SQR(A), P2.SQR(A), P3.SQR(A); for (int i = 0; i < n + n; i++) reduce(A[i] = get(P1[i], P2[i], P3[i]) + get(P1[i + n], P2[i + n], P3[i + n]) - mod); } inline void PW(int *res, int *base, int p) { init(n << 1); res[0] = 1, clear(res + 1, res + n); while (p) { if (p & 1) MUL(res, base); p >>= 1; if (p) SQR(base); } }#undef N}int f[8192], g[8192];int main() { scanf("%d%d", &n, &m); f[1] = f[n - 1] = 1; Poly::PW(g, f, m); printf("%d\n", g[0]); return 0;}