题目概述

HDU7232

解题报告

比赛的时候想的是正着做，写完DP式子发现是个看起来很可做的东西，结果实际上不能做，寄掉了。

实际上应该倒着做，$f_{i}$ 表示 $[1,n]$ 排列第一次出现在 $[i-n+1,i]$ 位置的方案数，那么最终答案就是 $n^m-\sum_{i=n}^{m}f_i\cdot n^{m-i}$ 。

考虑容斥转移（随便放，减去上次放和这次不重叠，减去上次放和这次重叠）：

$$ f_i=n^{i-j}n!-\sum_{j=n}^{i-n}f_j\cdot n^{i-j-n}n!-\sum_{j=i-n+1}^{i-1}f_j\cdot (i-j)! $$

由于 $f_i$ 下标从 $n$ 开始不方便，因此考虑令 $g_i=f_{i+n}$ ，则：

$$ g_i=n^i n!-\sum_{j=0}^{i-n}g_j\cdot n^{i-j-n}n!-\sum_{j=i-n+1}^{i-1}g_j\cdot (i-j)! $$

令 $G(x)$ 为 $g_i$ 的生成函数，令 $A(x)=\sum_{i=0}^{\infty}n^in!\cdot x^i,B(x)=\sum_{i=1}^{n-1}i!\cdot x^i$ ，则：

$$ G(x)=A(x)-x^nA(x)G(x)-B(x)G(x)\\ G(x)={A(x)\over 1+x^nA(x)+B(x)} $$

多项式求逆就行了。

示例程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=1<<19,MOD=998244353;

int te,n,m,fac[maxn+5],ans;
int wn[maxt+5],tem[maxt+5],A[maxt+5],B[maxt+5],G[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
struct fastO{
    int si;char buf[100000];
    fastO() {si=0;}
    void putc(char ch){
        if (si==100000) fwrite(buf,1,si,stdout),si=0;
        buf[si++]=ch;
    }
    ~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
    int len=0,buf[100];
    if (x<0) fo.putc('-'),x=-x;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) fo.putc(buf[--len]+48);
    fo.putc(ch);
}
inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
void Make(int n) {fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i);}
void NTTPre(){
    int x=Pow(3,(MOD-1)/maxt);
    wn[maxt/2]=1;
    for (int i=maxt/2+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x);
    for (int i=maxt/2-1;i>=0;i--) wn[i]=wn[i<<1];
}
void NTT(int *a,int n,int f){
    if (f>0){
        for (int k=n>>1;k;k>>=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=a[i+j+k];
                    a[i+j+k]=MUL(x+MOD-y,wn[k+j]);
                    a[i+j]=ADD(x,y);
                }
    } else {
        for (int k=1;k<n;k<<=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]);
                    a[i+j+k]=ADD(x,MOD-y);
                    a[i+j]=ADD(a[i+j],y);
                }
        for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV);
        reverse(a+1,a+n);
    }
}
void Inv(int *F,int *a,int n){ // F=1/a
    if (n==1) {F[0]=Pow(a[0],MOD-2);return;}
    Inv(F,a,n>>1);
    for (int i=0;i<n;i++) tem[i]=a[i],tem[i+n]=F[i+n]=0;
    NTT(tem,n<<1,1);NTT(F,n<<1,1);
    for (int i=0;i<(n<<1);i++) tem[i]=MUL(F[i],2+MOD-MUL(tem[i],F[i]));
    NTT(tem,n<<1,-1);for (int i=0;i<n;i++) F[i]=tem[i],F[i+n]=0;
}
int main(){
    Make(maxn);NTTPre();
    for (readi(te);te;te--){
        readi(n);readi(m);
        int K=m-n,t;for (t=1;t<=(K<<1);t<<=1);
        for (int i=0;i<t;i++) A[i]=B[i]=0;
        for (int i=0;i<=K;i++) A[i]=MUL(Pow(n,i),fac[n]);
        B[0]=1;for (int i=n;i<=K;i++) B[i]=A[i-n];
        for (int i=1;i<=K && i<n;i++) B[i]=ADD(B[i],fac[i]);
        Inv(G,B,t>>1);
        NTT(G,t,1);NTT(A,t,1);
        for (int i=0;i<t;i++) G[i]=MUL(G[i],A[i]);
        NTT(G,t,-1);
        ans=Pow(n,m);
        for (int i=n;i<=m;i++) ans=ADD(ans,MOD-MUL(G[i-n],Pow(n,m-i)));
        writei(ans);
    }
    return 0;
}