博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces Round #450 (Div. 2)D. Unusual Sequences[数论][组合数学][dp II]
阅读量:5955 次
发布时间:2019-06-19

本文共 1839 字,大约阅读时间需要 6 分钟。

题目:

题意:找到加和为m的且gcd为n的数列种类数

分析:可以转化为求gcd为1的加和为m/n的种类数,假设有m/n个1,则除了第一个以外的每个1可以选择和前面一项合并,也可以独立存在,故不考虑gcd总情况有$2^{(m/n-1)}$。

考虑过加和后,可以删除gcd为2,3,4……的情况,gcd为2的情况则为2个相同的gcd为1且加和为n/2的序列组合,3同理。所以找出除1以外的所有x的因子,减去相应的情况,使用记忆化搜索。

代码:

1 #define _CRT_SECURE_NO_DEPRECATE 2 #pragma comment(linker, "/STACK:102400000,102400000") 3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 #include
14 #include
15 #include
16 #include
17 #include
18 #include
19 #define pii pair
20 #define mod 100000000721 #define mp make_pair22 #define pi acos(-1)23 #define eps 0.0000000124 #define mst(a,i) memset(a,i,sizeof(a))25 #define all(n) n.begin(),n.end()26 #define lson(x) ((x<<1)) 27 #define rson(x) ((x<<1)|1) 28 #define inf 0x3f3f3f3f29 typedef long long ll;30 typedef unsigned long long ull;31 using namespace std;32 const int maxn = 1e5 + 5;33 map
dp;34 ll poww(ll m, int n)35 {36 ll ans = 1;37 ll temp = m%mod;38 while (n)39 {40 if (n & 1)41 ans *= temp;42 ans %= mod;43 temp *= temp;44 temp %= mod;45 n >>= 1;46 }47 return ans%mod;48 }49 ll getans(ll x)50 {51 if (dp.count(x))return dp[x];52 ll tempans = poww(2, x - 1);53 for (int i = 2; i*i <= x; ++i)54 {55 if (x%i == 0)tempans = (tempans - getans(x / i) + mod) % mod;56 if (x%i==0&&i*i != x)tempans = (tempans - getans(i) + mod) % mod;57 }58 tempans = (tempans - getans(1) + mod) % mod;59 return dp[x]=tempans;60 }61 62 int main()63 {64 ios::sync_with_stdio(false);65 cin.tie(0); cout.tie(0);66 int i, j, k, m, n;67 cin >> n >> m;68 if (m%n) { cout << "0" << endl; return 0; }69 dp[1] = 1;70 m /= n;71 ll ans = getans(m);72 cout << ans << endl;73 return 0;74 }

转载于:https://www.cnblogs.com/Meternal/p/8119821.html

你可能感兴趣的文章
面试题:在O(1)空间复杂度范围内对一个数组中前后连段有序数组进行归并排序...
查看>>
用ajax技术实现无闪烁定时刷新页面
查看>>
子进程清理
查看>>
HDU1022 Train Problem I
查看>>
微软已停止对Vista RTM(SP0)的服务支持
查看>>
Spring依赖检查
查看>>
第 72 章 FAQ
查看>>
Activity 切换 动画
查看>>
[LeetCode] Sum of Left Leaves 左子叶之和
查看>>
[LeetCode] Find Median from Data Stream
查看>>
3.6. Pure-FTPd + LDAP + MySQL + PGSQL + Virtual-Users + Quota
查看>>
50.9. 触发器(Trigger)
查看>>
9.3. where 优化
查看>>
《基于MFC的OpenGL编程》Part 18 Reading objects from the OBJ File Format
查看>>
Spring 文件上传功能
查看>>
RAC静默安装与DG搭建
查看>>
windows 下mysql的安装于使用(启动、关闭)
查看>>
Android 中文 API (28) —— CheckedTextView
查看>>
PHPStorm IDE 快捷键(MAC)
查看>>
反编译代码遇到的问题
查看>>