题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/10/test3_problem.pdf
官方题解：http://oi.cyo.ng/wp-content/uploads/2016/10/solution.pdf
这题做起来还是感觉很有意思的！
然而这™是NOIP模拟题！ (╯‵□′)╯︵┻━┻
详细的看题解吧！
题解的式子枚举的是并集的大小，我枚举的是交集的大小
反正都一样，式子搞出来都差不多！
另外下一次如果组合数表较小的话还是先预处理出来吧
这一份代码是现场算的，超级蛋疼！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100+9;
const int MOD = 998244353;
int n,m,p,q,POW[N],REV[N],g[N][N];
struct Matrix{
int a[N][N];
inline Matrix() {}
inline Matrix(const Matrix &B) {
memcpy(this,&B,sizeof(*this));
}
inline Matrix(int x) {
memset(a,0,sizeof(a));
for (int i=1;i<=n;i++) {
a[i][i] = x;
}
}
inline Matrix operator * (const Matrix &B) {
Matrix ret(0);
for (int j=1;j<=n;j++) {
for (int i=1;i<=n;i++) {
for (int k=1;k<=n;k++) {
ret.a[i][j] += (LL)a[k][j] * B.a[i][k] % MOD;
ret.a[i][j] %= MOD;
}
}
}
return ret;
}
inline Matrix operator ^ (int t) {
Matrix ret(1),tmp(*this);
while (t) {
if (t & 1) ret = ret * tmp;
tmp = tmp * tmp; t >>= 1;
}
return ret;
}
}trans,ans;
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline int pow(int w, int t) {
int ret = 1;
while (t) {
if (t&1) ret = (LL)ret * w % MOD;
w = (LL)w * w % MOD; t >>= 1;
}
return ret;
}
inline int alph(int a, int b, int x) {
if (x > a || x > b || p-a-b+x < 0) return 0;
int ret = (LL)POW[a] * POW[p-a] % MOD;
ret = (LL)ret * REV[x] % MOD;
ret = (LL)ret * REV[a-x] % MOD;
ret = (LL)ret * REV[b-x] % MOD;
ret = (LL)ret * REV[p-a-b+x] % MOD;
return ret;
}
int main(){
n = read(); m = read();
p = read(); q = read();
POW[0] = REV[0] = 1;
for (int i=1;i<=max(n,p);i++) {
POW[i] = (LL)POW[i-1] * i % MOD;
}
REV[max(n,p)] = pow(POW[max(n,p)],MOD-2);
for (int i=max(n,p)-1;i;i--) {
REV[i] = (LL)REV[i+1] * (i+1) % MOD;
}
g[1][1] = p;
for (int i=2;i<=n;i++) {
for (int j=1;j<=p;j++) {
g[i][j] = (LL)g[i-1][j-1] * (p - j + 1) % MOD + (LL)g[i-1][j] * j % MOD;
g[i][j] %= MOD;
}
}
for (int a=1;a<=n;a++) {
for (int b=1;b<=n;b++) {
if (a > p || b > p) continue;
for (int x=0;x<=a+b-q;x++) {
trans.a[b][a] += alph(a,b,x);
trans.a[b][a] %= MOD;
}
trans.a[b][a] = ((LL)g[n][b]*REV[p]%MOD) * trans.a[b][a] % MOD;
trans.a[b][a] = ((LL)POW[b]*POW[p-b]%MOD) * trans.a[b][a] % MOD;
}
}
for (int i=1;i<=min(n,p);i++) {
ans.a[i][1] = g[n][i];
}
trans = trans ^ (m-1);
ans = ans * trans;
int vout = 0;
for (int i=1;i<=n;i++) {
vout += ans.a[i][1];
vout %= MOD;
}
printf("%d\n",vout);
return 0;
}
Hello just wanted to give you a brief heads up and let you
know a few of the pictures aren’t loading properly. I’m not sure why but I think its a linking issue.
I’ve tried it in two different browsers and both show the same outcome.
This is really interesting, You’re a very skilled blogger.
I’ve joined your feed and look forward to seeking more of your
fantastic post. Also, I have shared your website in my social networks!
Hello, after reading this amazing paragraph i am too cheerful to share my experience here with friends.
We absolutely love your blog and find the majority
of your post’s to be exactly what I’m looking for. can you offer guest writers to write content to suit your
needs? I wouldn’t mind publishing a post or elaborating on a
lot of the subjects you write concerning here. Again, awesome blog!
Hi there, everything is going sound here and ofcourse every one is sharing information, that’s genuinely
fine, keep up writing.
It’s fantastic that you are getting ideas from this piece of writing as well as from our dialogue made here.
Excellent article. I’m experiencing a few of these issues as well..
Its such as you read my thoughts! You seem to understand
a lot approximately this, such as you wrote the e-book in it or something.
I feel that you just can do with some %
to force the message home a little bit, but other than that, that is
excellent blog. An excellent read. I will certainly be back.
Sweet blog! I found it while browsing on Yahoo News.
Do you have any tips on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem to get
there! Many thanks
I’m really enjoying the design and layout of
your site. It’s a very easy on the eyes which makes it much more enjoyable for me to come here and
visit more often. Did you hire out a designer to
create your theme? Excellent work!
I am really impressed with your writing skills and also with the layout on your weblog.
Is this a paid theme or did you modify it yourself?
Anyway keep up the excellent quality writing, it is
rare to see a great blog like this one today.
Thank you for the sensible critique. Me and my neighbor were just preparing to do some research about this. We got a grab a book from our area library but I think I learned more clear from this post. I am very glad to see such great information being shared freely out there.
Truly no matter if someone doesn’t know afterward its up
to other visitors that they will help, so here it happens.
Nice post. I learn something new and challenging on sites I stumbleupon every day.
It will always be helpful to read through content from other
authors and use a little something from their web sites.
Hurrah, that’s what I was searching for, what a data!
existing here at this weblog, thanks admin of this
site.
Very good information. Lucky me I recently
found your site by chance (stumbleupon). I’ve book-marked it for later!
Ahaa, its nice conversation regarding this paragraph here at this weblog, I have read all
that, so at this time me also commenting here.
Wow, fantastic weblog structure! How long have you ever been blogging for?
you make running a blog glance easy. The total look of your site is great, as neatly as the content!
For newest news you have to go to see world-wide-web and on world-wide-web
I found this website as a best website for hottest updates.
Its not my first time to pay a quick visit this web site, i
am visiting this site dailly and get good information from here all the time.
Valuable info. Lucky me I discovered your site accidentally,
and I’m shocked why this accident did not came about earlier!
I bookmarked it.
This is a very good tip particularly to those fresh to the blogosphere.
Simple but very accurate information… Thank you for sharing this one.
A must read post!
Very quickly this web site will be famous among
all blogging users, due to it’s pleasant posts
With every little thing which seems to be building within this area, a significant percentage of perspectives are actually somewhat refreshing. Nonetheless, I beg your pardon, but I do not give credence to your entire idea, all be it refreshing none the less. It seems to us that your opinions are actually not completely validated and in actuality you are your self not really entirely convinced of your assertion. In any case I did appreciate looking at it.