首页 > 代码库 > BZOJ4735: 你的生命已如风中残烛
BZOJ4735: 你的生命已如风中残烛
我先打了个暴力dfs 输出所有方案
发现看不懂
先不考虑普通卡的排列 然后求出答案 最后乘上 (n-m)!
然后再打一个暴力 dfs输出所有方案(雾)
然后找规律呗
我随便输入了几组数据
1 4 -> 5 = 5
1 5 -> 6 = 6
1 4 5 -> 90 = 9 * 10
2 4 5 -> 110 = 10 * 11
3 4 5 -> 132 = 11 * 12
1 3 6 -> 90 = 9 * 10
1 1 3 5 -> 720 = 8 * 9 * 10
发现好像当n相同时,答案只和 m有关 和wi无关
然后就找到规律了
233333333
tans = m*(m-1)*(m-2)...*(m-n+1)
然后ans = tans*(n-m)!
就好了
仔细看一下 答案好像是某种组合数 反正我推不出来
代码:
#include<cstdio> #include<cstring> #include<iostream> #define For(i,x,y) for(int i=x;i<=y;++i) using namespace std; const int P = 998244353; int n,m; int w[45]; long long res; bool vis[45]; int ans[1000]; void dfs(int step,int farest){ if(step==farest+1)return; if(step==m+1){ For(i,1,step-1){ printf("%d ",ans[i]); } puts(""); res++;return; } // ans[step]=0;dfs(step+1,farest); For(i,1,m){ if(vis[i])continue; vis[i]=1; ans[step]=w[i]; dfs(step+1,farest+w[i]); vis[i]=0; } } void brute_work(){ if(n==0){puts("0");return;} For(i,1,n) m+=w[i]; if(m==0){puts("0");return;} // dfs(1,1); // cout<<res<<endl; res=1; For(i,2,n) res=(1ll*res*(m-i+2))%P; For(i,1,m-n) res=(1ll*res*i)%P; printf("%lld",res);return; } int main() { cin>>n; For(i,1,n)scanf("%d",&w[i]); brute_work(); return 0; }
BZOJ4735: 你的生命已如风中残烛
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。