题目链接:https://www.luogu.org/problem/P4931。
蛮有意思的题,我一开始的想法是这样的:
设fk表示至少k对情侣坐在一起,那么考虑枚举这k对是怎么坐的,剩下的随便填,式子就是:
fk=(nk)22kk!(2n−2k)!
显然可以把恰好容斥出来,但是这样每次算都要O(n),复杂度就是O(Tn2),不太能过。
然后有一个很有意思的东西就是说,可以设fn表示n对情侣没有一对坐在一起的方案数,那么可以直接把答案表示出来:
ansn,k=(nk)22kk!fn−k
其实和上面是一样的,只是说这次填剩下的人的时候保证了两两不坐在一起,那么这个东西就是恰好。
注意到f不依赖于某个n,也就是说如果我们可以O(n2)算f,那么复杂度就降为了O(Tn+n2),可以通过没加强的版本。
算f有个比较显然的办法就是,还是用至少k个坐在一起的方案数去容斥,这次只需要容斥恰好0个坐在一起的方案数,那么容易写出式子:
fn=n∑i=0(−1)i(ni)22ii!(2n−2i)!
这样就可以通过未加强版了。
然后我就不会加强版了。。。
去瞄了一眼题解,发现有神仙使劲优化上面式子然后得到了递推式。。但是我太菜了没看懂。。。这里有个小清新的想法 看题解看来的:
现在忘记之前的容斥,我们考虑找到一个f的递推关系,我们枚举第一排坐的是谁,因为这俩不能是情侣所以有2n(2n−2)种情况,那么考虑对应的两个人是怎么坐的,有两种情况:
- 他们俩坐一起了,那么对其他人不影响了,方案数就是2(n−1)fn−2。
- 否则我们硬点他俩不能坐一起,方案数就是fn−1。
所以递推式就是fn=4n(n−1)fn−1+8n(n−1)2fn−2。
复杂度O(n+T)(针对加强版题面)。
给个加强版的代码:
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
| #include<bits/stdc++.h> using namespace std;
void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; }
void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double #define ll long long
#define pii pair<int,int > #define vec vector<int >
#define pb push_back #define mp make_pair #define fr first #define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e7+10; const int inf = 1e9; const lf eps = 1e-8; const int mod = 998244353;
int f[maxn],fac[maxn],ifac[maxn],pw2[maxn];
int qpow(int a,int x) { int res=1; for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod; return res; }
int c(int a,int b) {return 1ll*fac[a]*ifac[b]%mod*ifac[a-b]%mod;}
void gen() { int n=1e7;fac[0]=ifac[0]=pw2[0]=1; for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod,pw2[i]=1ll*pw2[i-1]*2%mod; ifac[n]=qpow(fac[n],mod-2); for(int i=n-1;i;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
f[0]=1,f[1]=0; for(int i=2;i<=n;i++) f[i]=2ll*i*2ll*(i-1)%mod*(f[i-1]+2ll*(i-1)*f[i-2]%mod)%mod; }
int main() { gen();int t;read(t); while(t--) { int n,i;read(n),read(i); write(1ll*c(n,i)*c(n,i)%mod*pw2[i]%mod*fac[i]%mod*f[n-i]%mod); } return 0; }
|